13

セットのリストが与えられた場合:

  • S_1 : [ 1, 2, 3, 4 ]
  • S_2 : [ 3, 4, 5, 6, 7 ]
  • S_3 : [ 8, 9, 10, 11 ]
  • S_4 : [ 1, 8, 12, 13 ]
  • S_5 : [ 6, 7, 14, 15, 16, 17 ]

少なくとも 2 つの要素を共有するすべてのセットをマージする最も効率的な方法は? これは連結成分の問題に似ていると思います。したがって、結果は次のようになります。

  • [ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 ユニオン S_2 ユニオン S_5)
  • [ 8, 9, 10, 11 ]
  • [ 1, 8, 12, 13 ] (S_4 は S_1 と 1 を共有し、S_3 と 8 を共有しますが、それぞれで 1 つの要素しか共有しないため、マージされません)

単純な実装は O(N^2) です。ここで、N はセットの数であり、これは私たちには機能しません。これは、何百万ものセットに対して効率的である必要があります。

4

5 に答える 5

3 
Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

私の頭は、これはオーダー (2N ln N) に関するものだと言っています。それを一粒の塩で取ってください。

于 2008-11-23T21:51:45.290 に答える
2

セット内の要素を並べ替えることができる場合は、セットでMergesortを使用することを検討できます。必要な唯一の変更は、マージ フェーズ中に重複をチェックすることです。見つかった場合は、重複を破棄します。マージソートは O(n*log(n)) であるため、単純な O(n^2) アルゴリズムと比較して速度が向上します。

ただし、実際に効果を発揮するには、ソートされたセットを維持し、ソートされた状態を維持する必要があります。これにより、ソート フェーズをスキップして、マージ フェーズに直接進むことができます。

于 2008-11-23T21:18:00.817 に答える
1

これを O(n^2) 未満で行う方法がわかりません。

すべてのセットを他のすべてのセットと比較して、2 つ以上の共有要素が含まれているかどうかを確認する必要があります。これは n*(n-1)/2 回の比較であるため、共有要素のチェックに一定の時間がかかる場合でも、O(n^2) になります。

並べ替えでは、単純な実装は O(n^2) ですが、順序付き比較の推移的な性質を利用できます (したがって、たとえば、クイックソートの下部パーティションの何も比較する必要がないことがわかっている場合、上部パーティションの何かと比較する必要があります)。 、すでにピボットと比較されているため）。これにより、並べ替えが O(n * log n) になります。

これはここでは当てはまりません。したがって、以前の比較の結果に基づいて比較をスキップできる特別なセットがない限り、通常は O(n^2) になります。

ポール。

于 2008-11-24T08:14:44.237 に答える
0

補足: これが発生する頻度によって異なります。ほとんどのセットのペアが少なくとも 2 つの要素を共有している場合は、比較を進めると同時に新しいセットを作成し、条件に一致しない場合は破棄するのが最も効率的です。ほとんどのペアが少なくとも 2 つの要素を共有していない場合は、条件が確認されるまで新しいセットの構築を延期する方が効率的かもしれません。

于 2008-11-23T21:23:56.717 に答える
0

要素が本質的に数値である場合、または自然に並べ替えることができる場合 (つまり、1、2、42 などの値を割り当てることができます)、マージされたセットで基数ソートを使用し、2 つ目を作成することをお勧めします。ユニークな要素を拾うために渡します。

このアルゴリズムは O(n) である必要があり、ビットごとのシフト演算子とビット マスクを使用して、基数の並べ替えをかなり最適化できます。私が取り組んでいたプロジェクトで同様のことをしたことがありますが、それは魅力のように機能します。

于 2008-11-23T21:41:13.220 に答える