[Python3]値の領域をまとめたlistの重複部分を無くした新しいlistを作りたい

Question

図のような1次元の複数の領域があり、始点のlistと終点のlistにそれぞれの領域の始点と終点の座標が格納されています。目標としては下の図の領域1と2のように重複している場所がある領域を統合して新しいlistを作りたいと思っています。2つの領域ならコードが思い浮かぶのですが3つ以上のn個の領域の場合をどういう風にコードを書けばいいのかわかりませんでした。もしも書き方やヒント(アルゴリズムの紹介など)を教えてもいいよという方がいらっしゃればご教授ください。

領域が二つの時に作った関数

def range_integrate(start_lis, end_lis):
    update_start_lis = []
    update_end_lis = []
    #値の領域が被っていない時
    if end_lis[1] < start_lis[0] or end_lis[0] < start_lis[1]:
        update_start_lis.extend(start_lis)
        update_end_lis.extend(end_lis)
    #1番目の領域の始点が2番目の領域に含まれており、終点が2番目の領域の外にある時
    elif start_lis[1] <= start_lis[0] and start_lis[0] <= end_lis[1] \
            and end_lis[1] < end_lis[0]:
        update_start_lis.append(start_lis[1])
        update_end_lis.append(end_lis[0])
    #1番目の領域が2番目の領域内にある時
    elif start_lis[1] <= start_lis[0] and end_lis[0] <= end_lis[1]:
        update_start_lis.append(start_lis[1])
        update_end_lis.append(end_lis[1])
    #1番目の領域が2番目の領域を全て含む時
    elif start_lis[0] < start_lis[1] and end_lis[1] < end_lis[0]:
        update_start_lis.append(start_lis[0])
        update_end_lis.append(start_lis[0])
    #1番目の領域の始点が2番目の領域の外にあり、終点が2番目の領域に含まれている時
    elif start_lis[0] < start_lis[1] and \
        start_lis[1] <= end_lis[0] and end_lis[0] <= start_lis[1]:
        update_start_lis.append(start_lis[0])
        update_end_lis.append(end_lis[1])
    return [update_start_lis, update_end_lis]

---

追記　たくさんの回答ありがとうございます！未熟者ゆえコードを理解するのに時間がかかって返答に時間がかかるかもしれません。申し訳ないです。

Comments

[ikapy]

領域1と領域2のリスト同士であれば、
list(set(領域1 + 領域2))
で良いのでは

[ppaul]

欲しいのはアルゴリズムであってコードではないということですね。
コードを書くなら3行で済むので、一応の動作確認まではしましたが、アルゴリズムを書くとなるとかなりの時間がかかります。
ネットで同じようなことが書いてあるのを探してみるのでしばらくお待ち下さい。

[fana]

（質問の「高評価」を押してみたんだけど，質問の評価値が＋の状態って何か意味があるのだろうか？　単に低評価への耐性となるだけ？）

Answer 1

どうやら整数限定で考えているみたいなので簡単な処理手順を考えた．

---

十分な範囲の整数値について点数を付けることを考える．
初期値は全て0点とする．
↓
全ての領域に関して，

• 左端の整数の点数を +1 する
• 右端の整数の点数を -1 する

ということを行う．

質問記載の３つの領域の例で，扱う整数の範囲を 0～9 とすれば，

初期の点数：
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
↓
上記の処理を行った後の点数：
{ 0, 1, 0, 1,-1,-1, 1, 0,-1, 0 }

ということ．

これを左側から累積していくと
{ 0, 1, 1, 2, 1, 0, 1, 1, 0, 0 }
となる．
この累積点数値を左側から見ていけば，

• 初めて正の値になる箇所として領域の左端が見つかり，
• その後で初めて0になる箇所として領域の右端が見つかる

（左端が出てきた回数だけ右端が出てきたらそこで１個の領域ができる）

Comments

[fana]

…といった感じでわかりやすく（かえってわかりにくいか？）書いたけど，

要は，　左端の値　と　右端の値　とを同一の数直線上でソートして小さい側から拾っていきながら，左端なら+, 右端なら- みたいなのをやればいいという話．
（※同値の存在に注意する必要はある．0になってもすぐに決断せずに次が同値かをチェックする）

そのようにするなら結局は整数に限定しなくてもよいということになる．

（ppaul氏の示した絵をそのまま解釈しただけなので，既に示された実装と話が被っているかも．そうである場合には，その旨を指摘して低評価を入れてください）

[lehshell]

性能の良いアルゴリズムですね。実装するとこんな感じでしょうか？
from itertools import accumulate

def range_integrate(start_lis, end_lis):
nums = [0] * (max(end_lis) + 1)
for n in start_lis:
nums[n] += 1
for n in end_lis:
nums[n] -= 1
nums = list(accumulate(nums))
update_start_lis = [i for i, n in enumerate(nums) if n == 1 and (i == 0 or i > 0 and nums[i-1] == 0)]
update_end_lis = [i for i, n in enumerate(nums) if n == 0 and i > 0 and nums[i-1] == 1]
return [update_start_lis, update_end_lis]

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis) # [1, 6]
print(update_end_lis) # [5, 8]

start_lis = [6, 2, 3]
end_lis = [10, 4, 7]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis) # [2]
print(update_end_lis) # [10]

[lehshell]

インデントに `` 使って書き直しました。
from itertools import accumulate

def range_integrate(start_lis, end_lis):
``nums = [0] * (max(end_lis) + 1)
``for n in start_lis:
````nums[n] += 1
``for n in end_lis:
````nums[n] -= 1
``nums = list(accumulate(nums))
``update_start_lis = [i for i, n in enumerate(nums) if n == 1 and (i == 0 or i > 0 and nums[i-1] == 0)]
``update_end_lis = [i for i, n in enumerate(nums) if n == 0 and i > 0 and nums[i-1] == 1]
``return [update_start_lis, update_end_lis]

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis) # [1, 6]
print(update_end_lis) # [5, 8]

start_lis = [6, 2, 3]
end_lis = [10, 4, 7]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis) # [2]
print(update_end_lis) # [10]

[fana]

> 実装するとこんな感じでしょうか？

私自身は Python が微塵もわからないので，
実装についての 判断(?)/評価(?) に関しては，わかる人におまかせしたい．

Answer 2

2つの領域ならコードが思い浮かぶのですが3つ以上のn個の領域の場合をどういう風にコードを書けばいいのかわかりませんでした。

２つならできるのであれば，

領域1と領域2, 領域1と領域3, ... と総当たりで２つの領域の組み合わせをチェックしては条件に見合えば２つを１個に統合する

というのを，統合が全く起きなくなるまで延々と繰り返せばよいのでは．

（とかいう話だと「いくらなんでも自明すぎる」と怒られるのかな？）

---

[追記]上記内容をアルゴリズムっぽく書いてみる

２つの領域リストSとRを用意する．
Sには最初に処理対象たる全ての領域データを突っ込む．Rは最初は空である．

Sの中身が空になるまで以下の手続きを繰り返し行う．
Sの中身が空になった時点で，Rの内容が結果となる．

手続き：

1. Sから領域を１つ取り出す．どれでもよい．取り出した領域をkと呼ぶことにしよう．
2. Sの中から，「kと統合すべき」領域(kと重複しているか，あるいはちょうど境界が一致しているようなやつ）を全て取り出す．
3. Step2.で１つ以上の領域群を取り出せた場合，それらとkを統合した１つの領域データを作ってそれをSに入れる．

Step2.で１つも領域を取り出せなかった場合には，kをRに入れる．

Comments

[algobeginner]

回答ありがとうございます！
恥ずかしい話ですが領域同士の全パターンを何度も比較して繰り返せば正解まで
たどり着けるんじゃないかって発想までは辿り着いたんですけど
そこからどうやって合成→最初に戻る→合成した領域を含んだ状態で
合成→……合成出来る組み合わせなしというコードを書けばいいのかが
思いつきませんでした。
こっちのやり方は整数じゃない領域にも対応してるので出来る方が良いのはわかるのですが…

[退会済みユーザー]

前提として、もし「はじめに与えられる各領域の始点と端点は、整数とは限らない」のであれば、（何らかの最適化は考えられるにせよ基本的には）fanaさんのおっしゃる「総当たり」な方法にならざるを得ないのかなと思いました。

[fana]

手続きっぽく書いてみましたぞ．

[fana]

Step2 は，「１個ずつ取り出しては，それをkに統合してkを更新してから次を取り出す」という形にしてもよいです．

要は

* とにかく手当たり次第に統合できるものを見つけたら統合する．（その順序がどうだろうが結果は変わらないので）
* 孤立した領域を見つけ次第，それはRに移す．

っていうだけの話．

[algobeginner]

追記ありがとうございます！
何となくコードの組み方のイメージが固まりそうな気がします。
特に2番目の工程が完全に浮かばなかったのでアドバイス助かります！
これで自分でもコードを組めるかもしれません。

Answer 3

アドバイスを元にプログラムを組んでみました。
領域内の整数を全てsetの中に入れて重複を排除した後
その数字の羅列を元に始点と終点のリストを作ってみました

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
integrate_set = set()
integrate_lis = []
update_start_lis = []
update_end_lis = []

#領域の中の整数を全てintegrate_setの中に入れる
for i in range(len(start_lis)):
    for j in range(start_lis[i], end_lis[i]):
        integrate_set.add(j)
#setで被った数字を取り除きそれをintegrate_lisの中に入れる
integrate_lis = list(integrate_set)
integrate_lis.sort()
#前後の数字を比較して始点のリストと終点のリストに加える
update_start_lis.append(integrate_lis[0])
for k in range(1, len(integrate_lis) - 1):
    if integrate_lis[k + 1] - integrate_lis[k] >= 2:
        update_end_lis.append(integrate_lis[k] + 1 )
    if integrate_lis[k] - integrate_lis[k - 1] >= 2:
        update_start_lis.append(integrate_lis[k])
update_end_lis.append(integrate_lis[-1] + 1)
print(update_start_lis, update_end_lis)

実際に出力されるデータ
[1, 6] [5, 8]

追記
integrate_lisをsortするコードを追加して小さい順に並んでない時に正常に動かない不具合を修正しました。

Answer 4

アルゴリズムを言葉で説明するのはとても面倒ですので、ヒントとしてグラフを載せておきます。

質問にある領域１，領域２、領域３と見比べてみてください。

追記

うまく動いたようで良かったですね。

最初に作ったコードを載せておきます。(defの行を入れたので一行増えています)
ご参考まで

>>> import pandas as pd
>>> left = [1, 3, 6]
>>> right = [4, 5, 8]
>>>
>>> import pandas as pd
>>> def unite(left, right):
...     df = pd.DataFrame({'x':left+right, 'w':[1]*len(left)+[-1]*len(right)}).sort_values('x')
...     df['cs'] = df['w'].cumsum()
...     return list(df[(df['w']==1) & (df['cs']==1)]['x']), list(df[(df['w']==-1) & (df['cs']==0)]['x'])
...
>>> unite(left, right)
([1, 6], [5, 8])

Comments

[algobeginner]

素晴らしいアドバイスありがとうございました！目から鱗が落ちました。
領域に含まれる整数を全てリストアップして一度でも含まれたことのある整数と
そうでない整数で場合分けする事によってリストアップが出来ると解釈しました。

[actorbug]

[1,3][3,5]のように、ある領域の終点と別の領域の始点が同じ座標だった場合に、
ソートで終点側が先に来てしまうと、領域が統合されないような気がします。
pandasについて詳しくないので、的外れな指摘でしたらすみません。

[ppaul]

そうかもしれませんね。
問題を見て10分ぐらいで作ったコードなので考慮漏れがあるかもしれません。
ちょっと考えてみます。

[ppaul]

>>> unite([1,3],[3,5])
([1], [5])
なので統合されていました。

[actorbug]

せっかくなのでpandasをインストールして試したところ、もう少し長い入力で問題が出ました。
>>> unite(list(range(10)), list(range(1, 11)))
([0, 7, 8], [7, 8, 10])
安定ソートにしてあげる必要がありそうです。
.sort_values('x', kind='stable')

Answer 5

fana さんのアルゴリズムの実装例です。
このアルゴリズムのコードがないのは寂しいので掲載しておきます。

from itertools import accumulate

def range_integrate(start_lis, end_lis):
    nums = [0] * (max(end_lis) + 1)
    for n in start_lis:
        nums[n] += 1
    for n in end_lis:
        nums[n] -= 1
    nums = list(accumulate(nums))
    update_start_lis = [i for i, n in enumerate(nums) if n == 1 and (i == 0 or nums[i-1] == 0)]
    update_end_lis = [i for i, n in enumerate(nums) if n == 0 and i > 0 and nums[i-1] == 1]
    return [update_start_lis, update_end_lis]

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis)  # [1, 6]
print(update_end_lis)    # [5, 8]

start_lis = [6, 2, 3]
end_lis = [10, 4, 7]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis)  # [2]
print(update_end_lis)    # [10]

Answer 6

最初少数にも対応した新しいコードを作ろうと思っていたのですが
fanaさんのアドバイスのおかげで整数限定バージョンの改良版が作れたので載せておきます。

start_lis = [1, 3, 6]
end_lis = [4, 5, 7]
integrate_set = set()
integrate_lis = []
update_start_lis = []
update_end_lis = []

#領域の中の0.5の倍数を全てintegrate_setの中に入れる
for i in range(len(start_lis)):
    for j in range(start_lis[i], end_lis[i]):
        integrate_set = integrate_set.union({j, j + 0.5})
    integrate_set.add(end_lis[i])

#setで被った数字を取り除きそれをintegrate_lisの中に入れる
integrate_lis = list(integrate_set)
integrate_lis.sort()
print(integrate_lis)

#前後の数字を比較して始点のリストと終点のリストに加える
update_start_lis.append(integrate_lis[0])
for k in range(1, len(integrate_lis) - 1):
    if integrate_lis[k + 1] - integrate_lis[k] >= 1:
        update_end_lis.append(integrate_lis[k])
    elif integrate_lis[k] - integrate_lis[k - 1] >= 1:
        update_start_lis.append(integrate_lis[k])
update_end_lis.append(integrate_lis[-1])
print(update_start_lis, update_end_lis)

---

今回は範囲を出力するために使われた数字の列も出力に入れてみました

実際に出力される値
[1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 6, 6.5, 7]
[1, 6] [5, 7]
判定は数字の次の列と比較して1以上離れていたらそれが終点
前の数字と比較して1以上離れていたら始点と判定してリストの中に入れております。
いつ出来るかはわかりませんがアドバイスを元に少数にも対応した
プログラムにも挑戦してみようと思います。

Comments

[fana]

ただの興味ですが，これ，何に使う用なんでしょうか？
差支え無ければ想定用途を教えていただきたく．

[algobeginner]

元々プログラムの問題を解いてて回答に該当する数字の範囲のリストを作る
ところまでは成功したのですが、これを被りなく出力する事が出来なくて
簡単な内容に置き換えた物を質問させて頂きました。
数学のxの条件式の問題で当たり前のようにやっている
該当の範囲を答える事がプログラム上で表現出来ないのは
流石にまずいと思ってアドバイスを募った次第です。

Answer 7

algobeginner さんのご指摘内容に対応しました。
１点が３重に重なるケースは考慮していましたが１点が２重で３つの領域が重なるケースが考慮漏れしておりました。

def merge_span(spans):
    newspans = []
    for tpl in spans:
        for i, nums in enumerate(newspans):
            if tpl[0] <= nums[0] <= tpl[1] or nums[0] <= tpl[0] <= nums[1]:
                newspans[i] = (min(nums[0], tpl[0]), max(nums[1], tpl[1]))
                newspans = merge_span(newspans)
                break
        else:
            newspans.append(tpl)
    return sorted(newspans)


def range_integrate(start_lis, end_lis):
    spans = [*zip(start_lis, end_lis)]
    return list(map(list, zip(*merge_span(spans))))

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis)  # [1, 6]
print(update_end_lis)    # [5, 8]

start_lis = [6, 2, 3]
end_lis = [10, 4, 7]
update_start_lis, update_end_lis = range_integrate(start_lis, end_lis)
print(update_start_lis)  # [2]
print(update_end_lis)    # [10]

以下最初の回答内容です。
参考

def range_integrate(start_lis, end_lis):
    spans = [*zip(start_lis, end_lis)]
    newspans = []
    for tpl in spans:
        for i, nums in enumerate(newspans):
            if tpl[0] <= nums[0] <= tpl[1] or nums[0] <= tpl[0] <= nums[1]:
                newspans[i] = (min(nums[0], tpl[0]), max(nums[1], tpl[1]))
                break
        else:
            newspans.append(tpl)
    return list(map(list, zip(*newspans)))

start_lis = [1, 3, 6]
end_lis = [4, 5, 8]
print(range_integrate(start_lis, end_lis))  # [[1, 6], [5, 8]]

Comments

[algobeginner]

回答ありがとうございます！じっくりコード読ませてもらいました。
領域のリストを一つずつ読み込んでマージを済ませたリストと比較して
被っていたら比較してる領域同士をマージして
既存のタプルと置き換えるコードですかね？
いろんな組み合わせを試してみた所
start_lis = [6, 2, 3]
end_lis = [10, 4, 7]を入力した場合
期待する出力は[[2, 10]]になると思うのですが
[[3, 2], [10, 4]]と出力されてしまいます。
比較対象のタプルと2回以上被るとこうなるのかもしれません。

[lehshell]

失礼しました。考慮漏れしておりました。ご指摘内容に対応しました。ご確認ください。

Answer 8

解決後に水を差すようで、えろうすんません。

面白い問題やったんで、algobeginnerさんの書きはったコードを使わせてもろうたんやけど、どうも期待値どおりにならんケースがありますねん。なので一応報告しとこ思いましたわ。

まず、こういう

spans_1 = [
  [0, 3], [1, 4], [2, 6], [5, 9], [7, 10], [8, 17], [16, 20],
]

7個の領域の持つリスト、spans_1 を作ります。spans_1の２番目以降の領域は、どれも始点が、ひとつ前の領域に含まれるので、これら７つの領域は統合されることで、ひとつの領域 [0, 20] になるものです。

次に、spans_1 に含まれる各領域を正の方向に1000移動した領域のリスト spans_2 を作ります。

spans_2 = [[start + 1000, end + 1000] for start, end in spans_1]

同様に、spans_1 に含まれる各領域を正の方向に2000移動した領域のリストspans_3 を作ります。

spans_3 = [[start + 2000, end + 2000] for start, end in spans_1]

そして、spans_1、spans_2、spans_3 を結合したリスト、target_spans を作ります。

target_spans = [*spans_1, *spans_2, *spans_3]

target_spans　は、７×３＝２１個の領域を含みます。

ほんで、この target_spans に対して、algobeginnerさんの書きはったコードやってみよ思いましたんや。期待値としては、マージ後の領域リストは、1000ずつ離れた３つの領域を含む

[[0, 20], [1000, 1020], [2000, 2020]]

となるはずやねん。そやからupdate_start_lis　が [0, 1000, 2000]　、update_end_lisが、[20, 1020, 2020]　になるので、

[0, 1000, 2000] [20, 1020, 2020]

という結果が出力されるもんやろ思いましたんや。なので

start_lis = [start for start, end in target_spans]
end_lis = [end for start, end in target_spans]

とやって、始点と終点のリストを作りまして、あとはalgobeginnerさんの書きはった、

integrate_set = set()
integrate_lis = []
update_start_lis = []
update_end_lis = []

#領域の中の整数を全てintegrate_setの中に入れる
for i in range(len(start_lis)):
    for j in range(start_lis[i], end_lis[i]):
        integrate_set.add(j)
#setで被った数字を取り除きそれをintegrate_lisの中に入れる
integrate_lis = list(integrate_set)
#前後の数字を比較して始点のリストと終点のリストに加える
update_start_lis.append(integrate_lis[0])
for k in range(1, len(integrate_lis) - 1):
    if integrate_lis[k + 1] - integrate_lis[k] >= 2:
        update_end_lis.append(integrate_lis[k] + 1 )
    if integrate_lis[k] - integrate_lis[k - 1] >= 2:
        update_start_lis.append(integrate_lis[k])
update_end_lis.append(integrate_lis[-1] + 1)
print(update_start_lis, update_end_lis)

としてみました。そしたら

[0, 2000] [20, 1020]

と出たんです。これ領域 [0, 20] と [2000, 1020] ゆう意味やんな？ [2000, 1020] は始点が終点よりも大きいし、どないになってしもたんや、思いましたわ。
ワテの使い方が間違うてるやと思いますんで、どこおかしいか教えたってください m(_ _)m よろしゅうたのんます〜

➡ 一応 上に書いた確認のコードは replitゆうWEBに挙げときました。 (Run 押してもろたらすぐ実行できるで。)

---

補足：

領域の始点、終点が整数とは限らない場合、どうなるんやろ？とモヤモヤしたもんで、作ってみました。参考になれば幸いですー

#
# 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)

➡ サンプル

（※上記のコード、だいぶ無駄なことをやってそうな気がするので、いつか直せるといいかなと思うてます。）

追記(2021/9/4)

上記の、領域の始点、終点が整数とは限らない場合のコードを以下の点で見直しました。（修正後のコードは、replitにも上げています。 実行するとテスト結果が出力されます。）

• get_merged_spans(spans) の中で、走査対象の領域リストを、リストの先頭要素の領域と、２番目以降の残りの領域リストに分けて、先頭の領域と、残りの領域リストの各領域とを統合するときに、残りの領域リストのすべてに対して統合を試みていたのは無駄だったので、ひとつでも統合できる領域がみつかったら置き換えて、その後は統合を試みないでループを抜けるように修正

• get_merged_spans(spans)で与えられる引数のspansを、各領域の中点の昇順にソートしてから、統合のループに入るようにした。

• merge(a, b) は、統合可否のフラグも返していたが、統合した領域のみを返し、統合できない場合はNoneを返すようにした。

上記の3点で修正コードが以下です。

#
# 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)

Comments

[algobeginner]

追加の回答ありがとうございます！
自分の所で実際にテストしてみた所setに入った時の
数字の羅列がきちんと小さい順になっていないのが問題だとわかりました。
よってintegrate_lis = list(integrate_set)の後にintegrate_lis.sort()を加えて
小さい順に並び変えるときちんとプログラムが想定通りに動きました。
回答のコードも書き直そうと思います。

[退会済みユーザー]

さっそくのご対応、ご返信ありがとうございます。期待値が出力されたのを確認できました！

[退会済みユーザー]

何度もすみません。

integrate_lis.sort()
を追加いただいたコードを

spans = [[1, 2], [3, 4]]
start_lis = [start for start, _ in spans] # => [1, 3]
end_lis = [end for _, end in spans] # => [2, 4]

で実行すると、[1,2] と [3,4] は統合されないので、期待される出力結果は、
もともとのstart_lisとend_lisから変わらずの

[1, 3] [2, 4]

になると思うんですが、やってみると、[1,2] と [3,4] を統合して [1,4] にした感じの

[1] [4]

が出力されました。（とはいえ、重箱のすみつつくようなケースですし、algobeginnerさんのコードの意図は理解できたので、対応とご返答はいつでもかまいません。）

[退会済みユーザー]

領域の始点、終点が整数とは限らん場合のコードを追記しました。そやけど、始点、終点は整数に限るという前提にした方が問題として美しい思いますわ。

[algobeginner]

コードのミスを確認しました！
例えば始点[1, 3] 終点[4, 6]の領域の場合普通に領域内の整数を羅列すると
{1, 2, 3, 4, 5, 6}となり3と4の境界線が判別出来ず[1] [6]と出力されてしまいます。
なのでその対策として一旦[1, 3]の場合{1, 2}、[4, 6]の場合{4, 5}と
1少ない整数を羅列した後出力する際1足して領域を表示する
プログラムを組んでおりました。
しかしそうすると領域の始点と終点の差が1の場合
羅列される数字の数が1つになり始点と終点の情報が判別できなくなるようです。
suwmn50799さんが追加で書いていただいたコードもじっくり読んでみます！
理解するのに時間を要するので返信は待たせてしまうかもしれません。

[fana]

（整数限定の話として）「整数を羅列してから拾い集める」という処理を考えておられるようですが，
羅列処理の時点で各整数が領域の｛始点，終点，内側｝のどこ由来の物なのか？という情報を失っている（＝自ら捨て去っている）としたら，そりゃ後段の拾い集め時点で見分けが付かなくなりますよね．
（要するに，それだけでは話として足りてない，ということですね．）

[fana]

質問文に提示されている例で言えば，
領域２の右端の値5 と 領域3の左端の値6 とは，その整数値だけで見ると「連続している」ことになるわけですが，実際には「連続している」と判断してはいけないわけです．

簡素な対策をするなら，領域２からの羅列結果が｛ 3, 3.5, 4, 4.5, 5｝ みたいな 0.5 単位になる世界で処理を考えれば良いかもしれません．
（これだと 5.5 の部分で隙間ができるので，領域2と3とを統合しなくなるハズ）

[algobeginner]

アドバイスありがとうございます！早速アドバイスを元に
領域の幅が1の領域にも対応した新しいコードを書いてみました！
fanaさんのアドバイスを元に少数にも対応したバージョンも挑戦しようと思ってます！

[退会済みユーザー]

algobeginnerさん
> コードのミスを確認しました！
とのことで、よかったです????

> suwmn50799さんが追加で書いていただいたコードもじっくり読んでみます！

おおきに〜。ありがとうございます〜。 かなり無駄なことをしていたので、改良したコードを追記しておきました。

楽しい質問、ありがとうございました！