3

集合S = {s i : {z j : z ∈ N } } が与えられた場合、 Sの部分集合の共通部分の一意の集合を計算するための時間効率の良いアルゴリズムは何ですか?

背景として、私はこの問題のいくつかのバージョンを扱っていますが、いくつかは他よりも大きくなっています。最小のもので | さ| ≈ 1,000、|s i | ≈ 10,000 で、値は郵便番号です。

わかりやすくするための小さな例:

入力: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}}
出力: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}

| | さ| = 4 であり、 Sのサブセットは 2 4 = 16 あります。ただし、サブセット交差の一意のセットは 5 つしかありません。最初の 4 つはS自身のメンバーです。5 番目は {3} です。空集合は既にSのメンバーです。他の 10 個の部分集合の交差もすべて空集合を生成します。

4

2 に答える 2

2

これは、価値があるかもしれない高速な前処理ステップです。

すべての集合 s iについて、x と y の両方が s iに属しているか、どちらも属していない場合、要素 x と y を等価と呼びます。各等価クラスの 1 つの代表を除くすべての要素を削除して、問題を単純化します。最後に、各代表者をそのクラスに展開します。

簡単にするために、各要素からその等価クラスのラベルへのマップを維持しながら、セットを 1 つずつスキャンします。等価性は、これまでに処理されたセットに関して決定されます。最初は、すべての要素が同じクラスにあるため、このマップは各要素を同じラベルに送信します。セットを処理するには、新しいラベルの空のマップを初期化します。セット内の各要素 x について、k を x の現在のラベルとします。キー k が新しいラベル マップに存在する場合、k に対応する値が x の新しいラベルになります。それ以外の場合は、新しいラベルを割り当てて x に割り当て、k から新しいラベルへのマッピングを追加します。

入力に対する実行は次のとおりです。

  1. 初期ラベル = {1: a, 2: a, 3: a, 4: a, 5: a, 6: a, 7: a, 8: a, 9: a, 10: a}.
  2. {} をスキャンします。何も起こりません。
  3. {1} をスキャンします。ラベル[1]をbに変更します。
  4. {2, 3} をスキャンします。label[2] と label[3] を c に変更します。
  5. {3, 4, 5, 6, 7, 8, 9, 10} をスキャンします。label[3] を d に、label[4..10] を e に変更します。
  6. 最後に、ラベル = {1: b, 2: c, 3: d, 4: e, 5: e, 6: e, 7: e, 8: e, 9: e, 10: e}. クラスを表すために、1 (b) と 2 (c) および 3 (d) と 4 (e) を選択します。その他はすべて削除されます。
于 2013-04-04T13:30:10.453 に答える
0

漸近的な時間の複雑さ:

n:実行中に変化するセットの数

m:平均セットサイズ

時間: T(Search-Matching-Sets) x T(Intersection) x SUM { k } for k: 1..n

時間: 2m x 2m x 1/2 n(n+1)

時間: O(4 m^2 x 1/2 nx (n+1)) ~ O(n^2 m^2)

提案されたアルゴリズム:

FOR i: 1..n
{

    FOR j: i..n
    {

        IF i = j THEN SKIP

        INTERSECTION := FIND-INTERSECTION ( SETS[i], SETS[j] )

        IF INTERSECTION ⊄ SETS[] THEN ADD INTERSECTION TO SETS[]

    }

}
于 2013-04-04T08:34:21.217 に答える