質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.68%

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

解決済

回答 2

投稿 編集

  • 評価 0
  • クリップ 0
  • VIEW 72

score 14

イメージ説明
図のような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]
  • クリップを取り消します

  • 質問の評価を上げたことを取り消します

  • 質問の評価を下げたことを取り消します

質問への追記・修正、ベストアンサー選択の依頼

回答 2

checkベストアンサー

+1

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

イメージ説明

質問にある領域1,領域2、領域3と見比べてみてください。

投稿

ppaul

ユーザーランキング月間1位

score 13347

  • algobeginner

    algobeginner

    2021/09/01 18:32

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

0

アドバイスを元にプログラムを組んでみました。
領域内の整数を全て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)
#前後の数字を比較して始点のリストと終点のリストに加える
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]

投稿

編集

algobeginner

score 14

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.68%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る