私はタプルの長いリストを持っている

Question

リストに共通の値に基づいてタプルのリストを組み合わせる方法、例えば次のようになります。彼らは何かを共有している場合

[('5','9'), ('10','11'), ('1','2'), ('1','3'), ('1','4'), ('2','7'), ('3','8'), ('2','1'), ('3','1'), ('3','4'), ('5','6'), ('5','10'), ('10','12'), ('11','13'), ('13','14')] 

は私がリストにそれらを結合する必要があります一般。だから、例の出力は次のようになります。

['11', '10', '13', '12', '14', '5', '6', '9'] 
['1', '3', '2', '4', '7', '8'] 

明確にする：入力はタプルのリストです。私は共有要素を持つすべてのタプルを1つのリストに結合する必要があります。それで、もし私が（1、2、（1、3）、（1、4）、（4、5））、要素はタプルを介してリンクされているため、['1'、 '2'、 '3'、 '4'、 '5']のリストにすべて入れなければなりません。

私は辞書を通って何かを思いついたが、悲惨に失敗しました。私は確かにいくつかの "より簡単な"ソリューションです。

あなたは労働組合・検索操作を行っているよう マーティン

Answer 1

が見えるお願いします。 https://en.wikipedia.org/wiki/Disjoint-set_data_structure

まず、リスト内に番号が付いたシングルトン・ディスジョイント・セットを作成します。次に、各タプルに対して、タプル内の数字に対応するセットを結合します。

上記のソリューションは、タプルの数がほぼ直線的になります。 union-findの実装については、A set union find algorithmを参照してください。

Answer 2

この問題は、無向グラフで接続されたコンポーネントを見つけることと同じようにフレーム化できます。リストに表示されるすべての異なる数字は、グラフのノード（頂点）として扱い、ペアをそのエッジとして扱うことができます。ここで

はインラインコメントを単純なアルゴリズムです：

l = [('5','9'), ('10','11'), ('1','2'), ('1','3'), ('1','4'), ('2','7'), ('3','8'), ('2','1'), ('3','1'), ('3','4'), ('5','6'), ('5','10'), ('10','12'), ('11','13'), ('13','14')] 

# get all unique elements ("nodes") of `l' 
nodes = set().union(*map(set, l)) 

# start with each node in its own connected component 
comp = {node:{node} for node in nodes} 

# now repeatedly merge pairs of components connected by edges in `l' 
while True: 
    merged = False 
    new_l = [] # will drop edges that have already been used in a merge 
    for n1, n2 in l: 
    if comp[n1] is not comp[n2]: 
     # the two connected components are not the same, so merge them 
     new_comp = comp[n1] | comp[n2] 
     for n in new_comp: 
     comp[n] = new_comp 
     merged = True 
    else: 
     # keep the pair for the next iteration 
     new_l.append((n1, n2)) 
    if not merged: 
    # all done 
    break 
    l = new_l 

# now print all distinct connected components 
for c in set(map(frozenset, comp.values())): 
    print list(c) 

これはアウト出力します

['1', '3', '2', '4', '7', '8'] 
['11', '10', '13', '12', '14', '5', '6', '9']