このコンテンツの比較に共通のアルゴリズムはありますか？これは何と呼ばれていますか？

Question

私はPythonでコーディングしています。

私はセットのリストを持っています。これらの集合は整数を含む。 2つのセットが整数項目を共有する場合、それは「接続」されます。私の目標は、これらのセットのすべてがすべて、相互接続されたセットまたは相互に接続されたセットの複数のグループとは対照的に、単一のグループにすべて相互に接続されているかどうかを判断することです。

共通のアルゴリズムがありますか？それは広く適用可能な目標のようです。

これは私の提案されたソリューションです：最初のセットで

開始し、内容が他のセット

共有コンテンツとの任意のセットを削除し、他のコンテンツを追加して共有されているかどうかを確認するには最初の設定

繰り返し変化がないまでに最初にすべての他のセットが削除された場合は、その後、彼らはすべての に接続されている

設定私は、各セットが互いに接続されている場合、単純にチェックし、相互に接続されたセットだから、

o--o--o o--o--o 

の別々のグループからセット

o--o--o--o--o--o 

の1本の相互接続チェーンを区別したい明確化

セットでは不十分です。ここで

Answer 1

あなたの解決策が正しいこと、およびDFSの変種である（あなたがセットを操作するのでかかわらず、それは少し非効率的であるかもしれない）

あなたの問題は、基本的にgraphがあるグラフの問題、次のとおりです。

G = (V,E) 
V = { sets } = {S1, S2, ..., Sn} 
E = { (Si,Sj) | Si and Sj share an integer } 

このグラフは無関係ですが、接続されているかどうかを確認するのが問題です。これは、BFSまたはDFSで行うことができます。 「固定」するまで（新しいソースから再起動せずに）、任意の頂点から開始してください。もしそれが起こると、あなたはすべてのセットを "発見"し、グラフが接続されます。それ以外の場合は、そうではありません。

実行時間が|V|あなたが持っているセットの数であり、|E|は、接続の数であり、O(|V|+|E|)です。

注：Eは、inverted indexを作成することで、スパースグラフに対して効率的に計算できます。各数値に対して、この数値を含むすべてのセットのリストを作成します（これは入力のサイズに沿っています）。リスト内のすべてのペアを通過してエッジを生成します（スパースグラフの場合、 。
密度の高いグラフの場合、より効率的なグラフを生成するには、すべてのペアのペアを調べるだけです。

Answer 2

は、私がしようとするものです。

• は、各セットのペアを通過します。

• がセットメンバーのそれぞれを比較：

• 共通の整数があるならば、1セットを離れて、別のを続け、これ以上のセットがなくなるまでこれを続けます。

• breakよりもメンバが共有されておらず、falseを出力している場合。

Answer 3

可能整数が知られており、その数は32のように結合した小上部を有し、あなたはビットのベクトルとして設定し、と、このようなビット単位で各適用を表すことができる場合：s(n)とx(n) = x(n-1) & s(n)は、n番目の組と&ビーイングでありますビットごとにとです。 nのビットがすべてx(n)の場合、すべてのビットが0の場合、複数のグループがあることがわかります。このアプローチの時間複雑さは線形であり、現在のハードウェアが非常に効率的に実行できる操作を使用します。

このソリューションおよびその他のソリューションは、次の点を確認することで拡張できます。元のソリューションの前に適用する必要があります。この考えは、場合によってはすばやく終了することです。このチェックでは、各セットの最小および最大の整数がわかっている必要があります。これらの最小整数の最大値がすべての最大整数の最小値より大きい場合、複数のグループの集合があることがわかります。だから、この場合、あなたは終えることができます。条件が真でない場合は、元のソリューションを続行する必要があります。