3

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

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

たとえば、人物 A と人物 B が同じ SSN を持っている場合、セット i を作成します。次に、人物 B と人物 C が同じ DLN を持っている場合、セットを作成します ii. 人物 D と E は同じ SSN を持っていますが、それ (および他のすべての識別子) は、人物 A、B、または C の識別子のいずれとも一致しません。すべての交差するサブセットをマージした後、人物 A、B、C の 1 つのセットになります。人物D、Eとの別のセット。

これが私のソリューションの疑似コードです。可能性のあるすべての交差セットをマージするより効率的な方法を誰かがすでに考え出していないかどうか、私は興味があります。セット間のリンクは X 人の長さになる可能性があることに注意してください (つまり、A は SSN で B に一致し、B は DLN で C に一致し、C は SSN で D に一致し、D は他の識別子で E に一致し、1 つのセットで人 AE になります)。また、これが実装される言語がセット操作をサポートしていると仮定します。

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
4

5 に答える 5

4

元の投稿での私のコメントを拡張するには、特定のセットの各メンバーがそのセットの少なくとも 1 つの他のメンバーと少なくとも 1 つの属性を共有するセットのリストを作成する必要があります。

単純に、これは、属性を共有するすべてのペアを見つけ、同じパートナーを持つペアを繰り返しマージすることで解決できます。これは O(N^3) (ペアを反復する場合は N^2、メンバーシップを決定する場合は最大 N 個の個別のセット) になります。

この問題は、すべてのオブジェクトとすべての一意の属性値がノードであるグラフの連結成分を決定することと考えることができます。各オブジェクトは、その属性値のそれぞれに接続されます。そのグラフの設定には線形時間がかかり、幅優先または深さ優先検索を使用して線形時間で接続コンポーネントを決定できます。

于 2009-06-08T22:52:06.887 に答える
0 
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;
                }
            }
    }
}
于 2009-06-08T22:20:37.980 に答える
0

Person オブジェクトの属性のセットが比較的少ないと思います (検討している Person オブジェクトの数と比較して)。Person オブジェクトのリストを何度もたどる回数を減らしたい場合は、Person を取得し、その属性を既知の可能な接続のリストに入れ、次の Person に進むことができます。連続する各 Person で、それが以前の接続に接続されているかどうかを確認します。その場合は、その一意の属性を可能な接続に追加します。すべての Person オブジェクトを 1 回のパスで処理できる必要があります。結果にいくつかの接続されていないセットが含まれる可能性があるため、最初のグラフを作成した後で、接続されていない Person オブジェクトを調べる価値があるかもしれません。

于 2009-06-08T22:05:40.193 に答える
0

したがって、コレクションの例は次のようになります。

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 ) で実行されます。すべての属性値が異なる場合、最悪の動作が発生します。属性値間の共有が増えると、属性値セット ([23,42] など) の挿入とメンバーシップの決定にかかる時間が支配的な要因になるため、属性値セットは効率的である必要があります。

最適な素集合を使用する場合、各検索またはマージ操作は償却時間 O(α(n)) で実行されます。

したがって、反復ごとに、最大で n 個のマルチコレクションが存在します (これまでにマルチコレクションがマージされていない状況)。新しいコレクションをマルチコレクションに統合するには、マルチコレクション k セットのそれぞれに対して検索操作を実行して、マージするすべてのマルチコレクションを識別する必要があります。これには、O(nkα(n)) によって制限される時間がかかります。 . この方法で見つかった最大 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 ) によって制限されます。

于 2009-06-08T22:14:20.330 に答える
0

まず、識別子には固有の階層があり、上位の並べ替えの矛盾する識別子は、下位の並べ替えの同じ識​​別子を相殺しますか? たとえば、A と B が同じ SSN を持ち、B と C が同じ DLN を持ち、C と D が同じ SSN を持ち、A と B の SSN と一致しない場合、それは 2 つのグループまたは 1 つのグループがあることを意味しますか?

矛盾が問題ではないと仮定すると、ユーザー 57368 (不明な Google) が述べているように、等価クラスを扱っています。等価クラスの場合、人々はしばしばUnion-find構造に目を向けます。これらのユニオンを実行する方法については、A と B の両方が同じ SSN を持っている場合、直接リンク AB を持っていないと仮定するため、すぐには簡単ではありません。代わりに、セットは 2 種類の要素で構成されます。各(attribute type, attribute value) = attributeペアは要素です。sに対応する要素もありますobject。オブジェクトの属性のリストを反復処理するときは、 union を実行します(object, attribute)。

Union-find データ構造の重要な機能の 1 つは、結果の構造がセットを表すことです。「A はどの集合に入っているか」を問い合わせることができます。これで十分でない場合はお知らせください。結果を改善できます。

しかし、最も重要な機能は、アルゴリズムが各ユニオンおよびクエリ操作に対して一定時間の動作に似たものを持っていることです。

于 2009-06-09T23:08:45.230 に答える