共通の要素を含むセットをマージしますか？

Question

私は共通の要素でセットをマージしたいと思います。例えば

input = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]), frozenset([1,1000]), 
      frozenset([100, 200]), frozenset([100, 300, 400])]) 

結果：

set([frozenset([1,2,3,4,5,6,7,8, 1000]), frozenset([100,200,300,400])]) 

これは何を達成するための効率的な方法でしょうか？

Answer 1

これは私が試みたものです。まず、私は

result = set() 
while input:                 
    r = set(input.pop()) 
    for rr in input.copy(): 
     if rr & r:             
      input.remove(rr) 
      r.update(rr) 
    result.add(frozenset(r)) 

シンプルですが何か間違ったことをしたこのコードの問題は、マージが input.pop()のオーダーに応じて、完全ではないかもしれないということです。 input={frozenset([0, 1]), frozenset([2,3]), frozenset([1,2])}とし、3つの要素がポップアウトされ、この割り当て順でループされると、 results={frozenset([0,1,2]), frozenset([2,3])}となります。

次に、回答in this postを実装しました。最初に新しいグラフの隣接リストを構築し、各ノードはfrozenset要素の1つ（input）に対応します。共通の要素を共有する場合、2つのノード間にエッジが存在します（frozenset）。次に、この新しいグラフの接続されたコンポーネントを見つけるために深さの最初のグラフのトラバーサルが使用されます。

result, visited = set(), set() 
components = collections.defaultdict(list) 
adj_list = collections.defaultdict(list) 

def dft(node, key): 
    visited.add(node) 
    components[key].append(node) 
    for neighbor in adj_list[node]: 
     if neighbor not in visited: 
      dft(neighbor, key) 

for r1, r2 in itertools.combinations_with_replacement(input, 2): 
    if r1 & r2: 
     adj_list[r1].append(r2) 
     adj_list[r2].append(r1) 
for node in adj_list: 
    if node not in visited: 
     dft(node, node) 

for node, neighbors in components.iteritems(): 
    result.add(node.union(*neighbors)) 

Answer 2

は使用ビルトインset.union() - >set.intersection()の長さは、この答えは、あなたが欲しいものを実装する方法をハイレベルで説明して0より大きい

---

ある場合のみ結果が含まれます。特定のソリューションが必要な場合は、まず問題を解決するための努力を示す必要があります。