回答編集履歴

ソース修正

2021/09/04 03:23

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -335,3 +335,255 @@
 （※上記のコード、だいぶ無駄なことをやってそうな気がするので、いつか直せるといいかなと思うてます。）
+### 追記(2021/9/4)
+上記の、領域の始点、終点が整数とは限らない場合のコードを以下の点で見直しました。（修正後のコードは、[replitにも上げています。](https://replit.com/@suwmn50799/357204teratail) 実行するとテスト結果が出力されます。）
+- get_merged_spans(spans) の中で、走査対象の領域リストを、リストの先頭要素の領域と、２番目以降の残りの領域リストに分けて、先頭の領域と、残りの領域リストの各領域とを統合するときに、残りの領域リストのすべてに対して統合を試みていたのは無駄だったので、ひとつでも統合できる領域がみつかったら置き換えて、その後は統合を試みないでループを抜けるように修正
+- get_merged_spans(spans)で与えられる引数のspansを、各領域の中点の昇順にソートしてから、統合のループに入るようにした。
+- merge(a, b) は、統合可否のフラグも返していたが、統合した領域のみを返し、統合できない場合はNoneを返すようにした。
+上記の3点で修正コードが以下です。
+```python
+#
+# merge(a, b)
+#
+#   二つの領域 a, b を受け取り、　それらが統合できれば統合した領域を返す。
+#   統合できなければ、Noneを返す。
+#
+def merge(a, b):
+    # a が b を含む場合は a を返す
+    if a[0] <= b[0] and b[1] <= a[1]:
+        return a
+    # b が a を含む場合は、b を返す
+    if b[0] <= a[0] and a[1] <= b[1]:
+        return b
+    # 上記以外の場合で、共通部分を持つ場合
+    if a[0] <= b[1] and b[0] <= a[1]:
+        c0 = min([a[0], b[0]])
+        c1 = max([a[1], b[1]])
+        return [c0, c1]
+    # aとbが共通部分を持たない場合
+    return None
+#
+# get_merged_spans(spans)
+#
+#   領域のリストを受け取り、統合できる領域を統合し尽くした領域リストを返す。
+#   （※引数の spans を変更しない）
+#
+def get_merged_spans(spans):
+    # 引数の領域リストを各領域の中点で昇順ソートしたリストを作成し、走査対象のリストとする。
+    target_spans = sorted(spans, key=lambda span: (span[0] + span[1]) / 2)
+    # 統合され尽くした領域リストを初期化（このリストを完成させて返す。）
+    merged_spans = []
+    # 統合され尽くした領域リストを作るループ（外側のループ）
+    while True:
+        # 先頭の領域と、2番目以降の領域リストに分割
+        head, *rest = target_spans
+        # 2番目以降の領域リストが空である場合
+        if len(rest) == 0:
+            # 先頭の領域を、統合され尽くした領域リストに追加して、外側のループを抜ける
+            merged_spans.append(head)
+            break
+        # 先頭の領域と、2番目以降の各領域を統合するループ（内側のループ）
+        for i, span in enumerate(rest):
+            # 先頭の領域 head と、2番目以降の領域 span を統合を試みる。
+            merged_span = merge(head, span)
+            # 統合される場合、統合された領域で置き換えて、内側のループをbreakで抜ける。
+            if merged_span:
+                rest[i] = merged_span
+                break
+        # 先頭の領域が、2番目以降の領域のどれとも統合できなかった場合（内側のループをbreakで抜けなかった場合）
+        else:
+            # 先頭の領域を、統合され尽くした領域リストに追加
+            merged_spans.append(head)
+        # 走査対象のリストを２番目以降のリストに置き換えて、外側のループのはじめに戻る
+        target_spans = rest
+    # 統合され尽くした領域リストを返す。
+    return merged_spans
+if __name__ == '__main__':
+    from random import random, shuffle
+    # 統合すると [0, 20] になる 7 つの領域を含むリスト（端点はともに整数）
+    base_spans = [[0, 3], [2, 4], [1, 6], [5, 11], [7, 10], [8, 17], [16, 20],]
+    # テスト1: base_spansをシャッフルしたリスト
+    test1_spans = base_spans
+    shuffle(test1_spans)
+    result = get_merged_spans(test1_spans)
+    print(result)
+    # テスト2: base_spansの各領域の端点に0以上1未満の小数を加えてシャッフルしたリスト
+    test2_spans = [[a[0] + random(), a[1] + random()]  for a in base_spans]
+    shuffle(test2_spans)
+    result = get_merged_spans(test2_spans)
+    print(result)
+    # テスト3: base_spansを +1000 および +2000 移動した領域リストをbase_spansに追加したリスト
+    test3_spans = [
+        *base_spans,
+        *[[a[0] + 1000, a[1] + 1000]  for a in base_spans],
+        *[[a[0] + 2000, a[1] + 2000]  for a in base_spans]
+    ]
+    shuffle(test3_spans)
+    result = get_merged_spans(test3_spans)
+    print(result)
+    # テスト4: テスト3の対象リストの各領域の端点に0以上1未満の小数を加えてシャッフルしたリスト
+    test4_spans = [[a[0] + random(), a[1] + random()]  for a in test3_spans]
+    shuffle(test4_spans)
+    result = get_merged_spans(test4_spans)
+    print(result)
+```

ソース修正

2021/09/04 03:23

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -329,3 +329,9 @@
 ➡ [サンプル](https://replit.com/@suwmn50799/Si-357204-Shi-Shu-Dui-Ying#main.py)
+（※上記のコード、だいぶ無駄なことをやってそうな気がするので、いつか直せるといいかなと思うてます。）

ソース修正

2021/09/01 14:11

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -159,3 +159,173 @@
 ➡ 一応 上に書いた確認のコードは [replitゆうWEBに挙げときました。](https://replit.com/@suwmn50799/Si-357204-1) (Run 押してもろたらすぐ実行できるで。)
+---
+**補足：**
+領域の始点、終点が整数とは限らない場合、どうなるんやろ？とモヤモヤしたもんで、作ってみました。参考になれば幸いですー
+```python
+#
+# merge(a, b)： 2つの領域（閉区間） a と b を受け取り、以下のような2つの要素をもつタプルを返す関数
+# 　　第1要素: a と b に共通部分があった場合、True 。共通部分がなかった場合は False
+# 　　第2要素： a と b に共通部分があった場合は統合された領域。共通部分がなかった場合は b
+#
+def merge(a, b):
+    if a[0] <= b[1] and b[0] <= a[1]:
+        c0 = min([a[0], b[0]])
+        c1 = max([a[1], b[1]])
+        return True, [c0, c1]
+    elif a[0] <= b[0] and b[1] <= a[1]:
+        return True, a
+    elif b[0] <= a[0] and a[1] <= b[1]:
+        return True, b
+    return False, b
+#
+# get_merged_spans(spans):領域のリストを受け取り、それに含まれる領域を統合し尽くした領域のリストを返す
+#
+def get_merged_spans(spans):
+    merged_spans = []
+    while True:
+        head, *rest = spans
+        if len(rest) == 0:
+            merged_spans.append(head)
+            break
+        next_spans = [*map(lambda span: merge(head, span), rest)]
+        if any(flag for flag, _ in next_spans):
+            spans = [span for _, span in next_spans]
+        else:
+            merged_spans.append(head)
+            spans = rest
+    return sorted(merged_spans)
+# 以下テスト実行
+if __name__ == '__main__':
+  import random
+  # マージすると、[0, 20] になる 7個の（整数）領域のリスト
+  spans_1 = [
+    [0, 3], [1, 4], [2, 6], [5, 9], [7, 10], [8, 17], [16, 20],
+  ]
+  # spans_1 の各区間を、正方向に1000移動した区間のリスト
+  spans_2 = [[start + 1000, end + 1000] for start, end in spans_1]
+  # spans_1 の各区間を、正方向に200移動した区間のリスト
+  spans_3 = [[start + 2000, end + 2000] for start, end in spans_1]
+  # spans_1, spans_2, spans_3 を結合したリストを作る。（3×7=21個の閉区間を含む）
+  target_spans = [*spans_1, *spans_2, *spans_3]
+  # target_spansに含まれる全領域の始点と終点に、1未満で小数点以下最大3桁までのランダムな小数を加える。
+  target_spans = list(map(lambda span: [
+    span[0] + (int(random.random() * 1000) / 1000),
+    span[1] + (int(random.random() * 1000) / 1000),
+  ], target_spans))
+  # シャッフルする
+  random.shuffle(target_spans)
+  # マージされた領域のリストを取得する。
+  merged_spans = get_merged_spans(target_spans)
+  # マージされた領域の開始と終了のリストを作る
+  update_start_lis = [start for start, _ in merged_spans]
+  update_end_lis = [end for _, end in merged_spans]
+  print(update_start_lis, update_end_lis)
+```
+➡ [サンプル](https://replit.com/@suwmn50799/Si-357204-Shi-Shu-Dui-Ying#main.py)

ソース修正

2021/09/01 13:50

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -142,7 +142,11 @@
+```
-**[0, 2000] [20, 1020]**
+[0, 2000] [20, 1020]
+```
@@ -154,4 +158,4 @@
-➡ 一応 上に書いた確認のコードは [replitゆうWEBに挙げときました。](https://replit.com/@suwmn50799/Si-357204-1)
+➡ 一応 上に書いた確認のコードは [replitゆうWEBに挙げときました。](https://replit.com/@suwmn50799/Si-357204-1) (Run 押してもろたらすぐ実行できるで。)