類似の要素を持つ複数のサブセットを結合する最も速い方法は何ですか？

Question

私は、1から500の値（整数）を持つ500以上のサブセットを持つリストを持っています。私が取得したいコードを実行した後

{1, 2, 3 } 
{2, 3} 
{4, 5} 
{3, 6, 7} 
{7, 9} 
{8, 4} 
{10, 11} 

：だから私のようなものを持っている

{1, 2, 3, 6, 7, 9} 
{4, 5, 8} 
{10, 11} 

私は、彼らが交差する場合、彼らが一緒に結合され、各サブセットに各サブセットを比較して、簡単なコード[here]を書きました、そうでなければ。 小規模では大丈夫ですが、大量のデータがあればそれは永遠にかかります。

改善してもらえますか？

P.S.私は数学や論理学では強くない、大きなO表記は私にとってギリシャ語である。ごめんなさい。

Answer 1

接続されたコンポーネントをグラフで見つけようとしています。各入力セットは、完全に接続されたノードのセットを表しています。

sets = [{1, 2, 3 },{2, 3},{4, 5},{3, 6, 7},{7, 9},{8, 4},{10, 11}] 
allelts = set.union(*sets) 
components = {X: {X} for X in allelts} 
component = {X: X for X in allelts} 
for S in sets: 
    comp = sorted({component[X] for X in S}) 
    mergeto = comp[0] 
    for mergefrom in comp[1:]: 
     components[mergeto] |= components[mergefrom] 
     for X in components[mergefrom]: 
      component[X] = mergeto 
     del components[mergefrom] 

コンポーネントのリストを有する構成要素になる（それらの最小要素をキー）、及び成分は、各要素のための成分を貯蔵：

>>> print(components) 
{1: {1, 2, 3, 6, 7, 9}, 4: {8, 4, 5}, 10: {10, 11}} 
>>> print(component) 
{1: 1, 2: 1, 3: 1, 4: 4, 5: 4, 6: 1, 7: 1, 8: 4, 9: 1, 10: 10, 11: 10} 
>>>