Algorithmus für die Zusammenführung Sätze, die mindestens 2 Elemente teilen,

Question

In einer vorgegebenen Liste von Sätzen:

• 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]

Was ist der effizienteste Weg, um alle Sätze zu verschmelzen, die mindestens zwei Elemente teilen? Ich nehme an, dies zu einem angeschlossenen Komponente Problem ähnlich ist. So das Ergebnis wäre:

• [1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)
• [8, 9, 10, 11]
• [1, 8, 12, 13] (S_4 Aktien 1 mit S_1 und 8 mit S_3, aber nicht verschmolzen, weil sie nur in der jeweils ein Element teilen)

Die naive Implementierung ist O (N ^ 2), wobei N die Anzahl der Sätze ist, die für uns nicht durchführbar ist. Dies müßte für Millionen von Sätzen effizient sein.

Answer 1

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.

Mein Kopf sagt, das ist etwa Order (2N ln N). Nehmen Sie das mit einem Körnchen Salz.

Answer 2

Wenn Sie die Elemente in der Menge bestellen können, können Sie sich in mit Mergesort auf Die Sätze. Die einzige Modifikation erforderlich ist, ist nach Duplikaten während der Mischphase zu überprüfen. Wenn einer gefunden wird, muss das nur das Duplikat. Da mergesort O (n * log (n)) ist, wird diese Geschwindigkeit bieten imrpoved wenn sie auf die naive O Vergleich (n ^ 2) -Algorithmus.

Um jedoch wirklich effektiv zu sein, sollten Sie eine sortierte Satz zu halten und halten es sortiert, so dass Sie die Sortier Phase überspringen und direkt in die Mischphase gehen.

Answer 3

Ich sehe nicht, wie dies kann als O in weniger durchgeführt werden (n ^ 2).

muss jeder Satz zu jedem anderen verglichen werden, um zu sehen, ob sie 2 oder mehr Elemente geteilt. Das ist n * (n-1) / 2 Vergleiche, also O (n ^ 2), auch wenn die Prüfung für gemeinsam genutzte Elemente benötigt konstante Zeit.

In Sortierung, die naive Implementierung ist O (n ^ 2), aber Sie können die Vorteile der Transitivität geordneter Vergleich nehmen (so zum Beispiel wissen, dass Sie nichts in der unteren Teilung quicksort muss irgendetwas zu vergleichen in die obere Trennwand, wie es bereits mit dem Dreh verglichen). Dies ist, was zur Folge für O Sortierung (n * log n).

Dies gilt hier nicht. Also, es sei denn, es ist etwas Besonderes an den Sets, die uns Vergleiche überspringen können, basierend auf den Ergebnissen früherer Vergleiche, es wird O (n ^ 2) im Allgemeinen sein.

Paul.

Answer 4

Eine Seite Anmerkung: Es hängt davon ab, wie oft dies geschieht. Wenn die meisten Paare von Sätzen tun Aktien mindestens zwei Elemente, könnte es am effizientesten, den neuen Satz in der gleichen Zeit zu bauen, wie Sie durch den Vergleich verstärken, und werfen es weg, wenn sie es nicht tun entsprechen den Zustand. Wenn die meisten Paare nicht Aktie mindestens zwei Elemente, dann bis zur Bestätigung des Zustands des Gebäudes des neuen Satzes Aufschieben könnte effizienter sein.

Answer 5

Wenn Sie Ihre Elemente in der Natur numerisch sind, oder natürlich bestellt werden kann (dh. Sie einen Wert zuweisen können, wie beispielsweise 1, 2, 42 etc ...), würde ich vorschlagen, eine Radixsort auf die fusionierte Sätze verwenden, und macht einen zweiten Durchgang auf den einzigartigen Elemente aufzunehmen.

Dieser Algorithmus soll von O (n) sein, und Sie können den Radixsort ziemlich viel mit bitweise Shift-Operatoren und Bit-Masken optimieren. Ich habe etwas ähnliches für ein Projekt getan, was ich gerade arbeite, und es funktioniert wie ein Charme.