Partition eine Liste von Sätzen, die durch gemeinsame Elemente

Question

Hier ist die jist problem:Gegeben eine Liste von Sätzen, wie:

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ]

Zurückgeben einer Liste von Gruppen des sets, so, dass Sätze, die ein gemeinsames element in der gleichen Gruppe.

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ]

Hinweis: die stickeyness - set (6,12,13) nicht haben ein gemeinsames element mit (1,2,3), aber Sie setzen sich in der gleichen Gruppe, weil (5,2,6).

Um Angelegenheiten zu erschweren, sollte ich erwähnen, dass ich nicht wirklich an diese ordentlich legt, sondern vielmehr eine DB-Tabelle mit mehreren Millionen Zeilen, die wie folgt aussieht:

element | set_id
----------------
1       | 1
2       | 1
3       | 1
5       | 2
2       | 2
6       | 2

und so weiter.Also ich würde gerne eine Möglichkeit in SQL, aber ich würde gerne eine Allgemeine Richtung für die Lösung.

BEARBEITEN:Verändert die Tabelle-Spalte-Namen (element, set_id) anstelle von (key, group_id), um die Allgemeinen konsistenter.Beachten Sie, dass Kev Antwort verwendet der alten Spalte-Namen.

Answer 1

Das problem ist, genau die Berechnung des angeschlossenen Komponenten ein hypergraph:die ganzen zahlen sind die Eckpunkte, und die sets sind die hyperedges.Die gewöhnliche Weise der Berechnung der angeschlossenen Komponenten ist durch Flutung Sie eines nach dem anderen:

• für alle i = 1 to N do:
• wenn ich wurde getaggt von einigen j < ich, dann weiter (ich meine, fahren Sie mit dem nächsten i)
• sonst flood_from(ich,ich)

wo flood_from(i,j) definiert als

• für jede Menge S enthalten, die ich, wenn es nicht bereits markiert, die von j, dann:
• tag-En von j und für jedes element k von S, falls k nicht bereits mit Tags versehen, indem Sie j, markieren Sie es, indem Sie j ein, und rufen Sie flood_from(k,j)

Die tags der setzt dann geben Sie die angeschlossene Komponente, die Sie suchen.

---

In Bezug auf Datenbanken, die Algorithmus kann wie folgt ausgedrückt werden:fügen Sie eine TAG-Spalte in Ihrer Datenbank, und berechnen Sie die angeschlossene Komponente, die ich durch mache

• S = wählen Sie alle Zeilen, in denen " set_id == i
• set-TAG, die ich für die Zeilen in S
• S' = wählen Sie alle Zeilen aus, in denen das TAG nicht gesetzt ist, und wo-element in element(S)
• während S' ist nicht leer do
• - - - - - set-TAG, die ich für die Zeilen in S'
• ---- S" = alle Zeilen auswählen, wo-TAG nicht gesetzt ist, und wo-element in element(S')
• ---- S = S union S'
• ---- S' = S"
• Rückkehr set_id(S)

---

Eine weitere (theoretische) Möglichkeit die Darstellung dieser Algorithmus wäre zu sagen, dass Sie suchen, sind für den festen Punkte einer Abbildung:

• wenn A = {A₁, ..., A_n} ist eine Menge von Mengen, definieren, union(A) = A₁ union ...union_n
• wenn K = {k₁, ..., k_p} ist eine Menge von ganzen zahlen definieren, die vorkommen(K) = die Menge der Sätze, die schneiden K

Dann ist S ein Satz, der zusammenhangskomponente von S erhält man durch Iteration von (Fälle)o(union) auf, bis ein Fixpunkt erreicht ist:

1. K = S
2. K' = Fälle(union(K)).
3. if K == K', then return K else K = K' und gehe zu 2.

Answer 2

Man könnte es als ein Diagramm problem der set (1,2,3) mit dem Satz (5,2,6) über den 2.Und dann verwenden Sie ein standard-Algorithmus zur Ordnung der angeschlossenen sub-Graphen.

Hier ist eine schnelle python-Implementierung:

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]

#first find the links
for n in range(len(nodes)):
    for item in nodes[n]:
        for m in range(n+1, len(nodes)):
            if (item in nodes[m]):
                links[n].add(m)
                links[m].add(n)

sets = []
nodes_not_in_a_set = range(len(nodes))

while len(nodes_not_in_a_set) > 0:
    nodes_to_explore = [nodes_not_in_a_set.pop()]
    current_set = set()
    while len(nodes_to_explore) > 0:
        current_node = nodes_to_explore.pop()
        current_set.add(current_node)
        if current_node in nodes_not_in_a_set:
            nodes_not_in_a_set.remove(current_node)
        for l in links[current_node]:
            if l not in current_set and l not in nodes_to_explore:
                nodes_to_explore.append(l)
    if len(current_set) > 0:
        sets.append(current_set)

for s in sets:
    print [nodes[n] for n in s]

Ausgabe:

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]

Answer 3

Dies ist wahrscheinlich ziemlich ineffizient, aber es sollte funktionieren, zumindest:Beginnen Sie mit einer Taste, wählen Sie alle Gruppen mit der Taste wählen Sie alle Schlüssel von jenen Gruppen, wählen Sie alle Gruppen mit diesen Tasten, etc., und sobald ein Schritt fügt keine neuen Schlüssel oder Gruppen, Sie haben eine Liste aller Gruppen eines sub-Graphen.Schließen Sie diese und wiederholen Sie von Anfang an, bis Sie keine data-Links.

In Bezug auf die SQL-dies würde müssen eine gespeicherte Prozedur, denke ich.MIT REKURSIVEN könnte dir irgendwie helfen, aber ich habe keine Erfahrung mit ihm noch, und ich bin nicht sicher, es ist verfügbar auf Ihrer DB-backend.

Answer 4

Zu denken, nachdem dieser einige mehr, ich kam mit dieser:

1. Erstellen Sie eine Tabelle namens groups mit Spalten (group_id, set_id)
2. Sortieren sets Tabelle element.Nun sollte es leicht zu finden, doppelte Elemente.
3. Durchlaufen Sie die Sätze Tisch, und wenn Sie finden, ein doppeltes element zu tun:
   1. wenn eine der set_id Felder besteht in der groups Tabelle, fügen Sie die anderen mit dem gleichen group_id.
   2. Wenn weder set_id besteht in der groups Tabelle, erstellen Sie eine neue Gruppen-ID, und fügen Sie beide set_ids groups Tabelle.

Am Ende habe ich einen groups - Tabelle mit allen sets.

Dies ist nicht eine Reine SQL, doch scheint O(nlogn), also denke ich, kann ich mit Leben.

Matt Antwort scheint mehr richtig, aber ich bin mir nicht sicher, wie es zu implementieren, in meinem Fall.