すべての交差和集合

StackOverflow https://stackoverflow.com/questions/967064

質問

私は、すべての交差部分集合の和集合によって作成されたセットのリストを見つける必要があり、複数の属性を持つオブジェクトのリストを与えられた。

具体的にこれらは多くの属性を持つ各、Personオブジェクトです。私はそのようななどSSN、DLN、などユニークな識別子の一握りに基づいて「マスター」セットのリストを作成する必要があります。

人物Aと人物Bが同じSSNを持っている場合は、

たとえば、彼らはセットIを作成します。人物BとCは同じDLNを持っている場合はその後、彼らはセットIIを作成します。人物DとEは同じSSNを持っているが、それ（およびすべての他の識別子）を者A、B、CとIが一組で終わるであろうすべての交差部分集合をマージした後者A、BまたはCの識別子のいずれとも一致しません者D、Eとし、別のセット。

ここに私の解決策のための擬似コードです。誰もがすでにすべての可能な交差セットをマージする、より効率的な方法を打ち出している場合、私は好奇心旺盛です。セット間のリンク（すなわちAがSSNによってBに一致し、Bは、DLNによってCに一致し、Cは、SSNによってDに一致し、Dは、いくつかの他の識別子によってEに一致する一組内の人物A-Eをもたらすであろう）長いX者であってもよいことに留意してください。また、これはサポートで実装される言語は、操作を設定することを前提としています。

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end
役に立ちましたか？

解決

オリジナルのポストで私のコメントを拡張するために、あなたはそのセットの少なくとも1人の他のメンバーとの与えられたセット株式の各メンバーが、少なくとも1つの属性セットのリストを作成したい。

単純に、これは、属性を共有するすべてのペアを見つけ、繰り返し同じパートナーを持って一緒にペアをマージすることによって、のいずれかを解決することができます。これはO（N ^ 3）（N ^ 2メンバーシップを決定するために、ペア上、及びN別個のセットまでの反復のために）であろう。

また、グラフ連結成分を決定するものとして、この問題を考えることができます>、すべてのオブジェクトとすべてのユニークな属性値がノードです。各オブジェクトは、その属性値のそれぞれに接続されます。そのグラフを設定すると、線形時間がかかるだろう、そしてあなたは、広さや深さ最初の検索で線形時間で連結成分を決定することができる。

他のヒント

私は（人の数はあなたが検討しているオブジェクトと比較して）あなたはPersonオブジェクトの属性の比較的小規模なセットを持っていることを推測します。あなたは人のリストが複数回オブジェクトを横断減らしたい場合、あなたは、人を取り、既知の可能な接続のリストにその属性を配置し、次の人に移動することができます。それは任意の接続前に接続されている場合、それぞれの連続した人と、あなたが参照してください。もしそうなら、あなたは可能な接続に独自の属性を追加します。あなたは1回のパスですべてのPersonオブジェクトを処理することができるはずです。それはあなたが最初のグラフを作成した後、それが接続されていないPersonオブジェクトを調べる価値があるかもしれないので、あなたは、結果にいくつかの切断のセットを持っているだろうことが可能です。

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

まず、識別子でいくつかの固有の階層があり、下ソートの高いソート相殺同じ識別子の識別子を矛盾するのですか？例えば、AとBは同じSSN、B及びCは同じDLNを有し、C及びDは、その2つのグループまたは1つがあることを意味し、AとBのSSNと一致しない同じSSNを持っている場合

と仮定すると、矛盾は、ユーザー57368（不明グーグル）状態として、等価クラスを扱っている、重要ではありません。等価クラスのために、人々はしばしば連合見つけるの構造に目を向けます。私はAとBの両方が同じSSNを持っているときに直接リンクA-Bを持っていないと仮定しているため、これらの組合を行う方法としては、それはすぐに些細ではありません。代わりに、私たちのセットは、2種類の要素で構成されます。各(attribute type, attribute value) = attributeペアは要素です。またobjectsに対応する要素を持っています。あなたがオブジェクトの属性のリストを反復すると、組合(object, attribute)を行います。

ユニオン検索するデータ構造の重要な特徴の一つは、得られた構造は、集合を表すことです。それは「である何セット？」照会することができますこれが十分でない場合は、私たちが知っていると我々は結果を改善することができます。

しかし、最も重要な特徴は、アルゴリズムは、各組合とクエリ操作のために一定時間の動作に似ている何かを持っているということです。

だからあなたのコレクションの例は、このようになります：

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

それから私は、あなたがインクリメンタルマルチコレクションに各コレクションをマージまたは挿入することにより、マルチコレクションを構築するアルゴリズムを使用することをお勧めします

反復1.最初のコレクションは、マルチコレクションなる

{A} { ss |-> [42], dl |-> [123] }

反復2. SSNが既に存在しているので、最初に次のコレクションをマージ

{A,B} { ss |-> [42], dl |-> [123,456] }

反復3. DLNがすでにあることから、再びマージます：

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

反復4.一致がないので、新しいマルチコレクションを挿入します：

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

反復5 SSNがあるので、第2のマルチコレクションをマージ

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

各繰り返し（各コレクションの1）で、あなたが処理されているコレクションと共通の値を持つのすべてのの多コレクションを識別しなければならない、とをマージするように、すべてのの一緒にこれらます。

属性の定数k個のnコレクションそれぞれが存在する場合、

一般的に、このアルゴリズムは、時間O（NNK）= O（N 2 ）で実行されます。すべての属性値が異なっている場合は、最悪の場合の挙動がexibitedされます。属性値の間に複数の共有がある場合、それは（[23,42]など）属性値セットのメンバーシップを挿入し、決定するために要する時間は、支配的な因子であることを得るので、属性値セットが効率的であるべきです。

あなたは最適な互いに素な集合を使用する場合は、

、その後、各検索またはマージ操作が実行されます償却時間O（α（N））

このように、それぞれに最大nマルチコレクション（無マルチコレクションがこれまでにマージされていない状況）であるだろうイテレーション。マルチコレクションに新しいコレクションを統合するには、マルチコレクションがO（nkα（N））で囲まれた時間をとる、マージするすべてのマルチコレクションを識別するためにセットをk個のそれぞれに検索操作を実行する必要があります。最もKマルチコレクションにマージすることは、この方法はO（K 2 α（N））を取るが見つかりました。

時間反復全てがO（N（nkα（N）+ K 2 α（N）））= O（N（nkα（N）））= O（によって囲まれているためだからN 2 Kα（N））= O（N 2 α（N））ここで、kは定数であるからである。

すべての実用的な目的のためにα（n）をも一定であるため、

、合計時間はO（N 2 ）で囲まれている。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top