Sammlung von Sätzen keine Sets enthalten, die eine Untergruppe von einem anderen in der Sammlung

Question

Ich suche eine abstrakte Datenstruktur, die eine Sammlung von Sätzen so darstellt, dass kein Satz in der Sammlung eine Teilmenge eines anderen Satzes in der Sammlung ist.

Das bedeutet, dass auf dem Einsatz folgende Bedingungen erfüllt werden:

A. Einfügen eines Elements, das bereits eine Teilmenge eines anderen Elements ist, wird die ursprüngliche Sammlung zurück.

B. Einfügen eines Elements, das eine Obermenge von irgendwelchen anderen Elementen ist in einer Sammlung mit dem Obermenge führen wird hinzugefügt, und die Untergruppen entfernt.

eine Ordnung auf den Elementen des Satzes Unter der Annahme, dann kann ein Präfix-Baum verwendet werden, um die Sammlung zu repräsentieren. Dies erlaubt Zustand A werden sehr schnell bearbeitet (dh es dauert nicht mehr um den Zustand zu überprüfen, als wäre es die Teilmenge einzufügen) jedoch Erfüllen der Bedingung B braucht Zeit.

Ich frage mich, ob es Datenstruktur, die B schnell als auch erfüllt werden kann.

Answer 1

Der triviale Ansatz wäre, eine Liste von Sätzen zu halten und eine lineare Suche durch, dass für jeden eingehenden Satz durchführt (Prüfung, ob die eingehenden eine Teilmenge ist).

Dies läuft offensichtlich in O (n) Zeit für die lineare Suche und möglicherweise O (m) Größe für die Größe des eingehenden Satzes. Somit O (n * m) Gesamtzeit (Anzahl der Sätze vs. Größe von jedem Satz).

Die naheliegendste Optimierung, ist natürlich auf Set-Größen zu indizieren. Dann testen Sie jeden eingehenden Satz gegen solche, die von gleich oder größer sind. (Ein Satz kann nicht eine Teilmenge von jeder kleineren Menge, duh!).

Die nächste Optimierung, die den Sinn kommt, ist in Index von Elementen zu erstellen. Damit für jeden eingehenden Satz würden Sie den Schnittpunkt der einzelnen Sätze jedes der Elemente enthalten, finden. Mit anderen Worten, wenn für eingehende Menge {a, b, c}, wir dieses Element finden {a} existiert in Mengen A, B und D, Element {b} existiert in B, E und F und {c} existiert in A, B, und Z ... dann dem ankommenden Satz eine Teilmenge von B ist (der Schnittpunkt der {A, B, D}, {B, E, F}, und {A, B, Z}).

Also, das klingt wie O (m * log (n)) Komplexität zu mir. (Wir müssen Hash-Suchen durchführen auf jedem Element jedes eingehenden Satz). Einfügungen sollte auch sein, die gleiche Reihenfolge (Einsetzen der neuen Set-ID in jedem der Element Karten). (In Big-O-Analyse 2 * O (m log (n)) reduziert bis auf O (m log (n)), natürlich).

Answer 2

Eine triviale Idee, die in O arbeiten wird (K), wobei K eine Größe von Element hinzugefügt wird.

• halten Sätze in welcher Weise auch immer u wollen
• keep Karte set_id -> set_size
• keep Karte Objekt -> set_id

sowohl A als auch B die Bedeutung O (K).

Answer 3

Wenn die einzelnen Mitglieder Ihrer Sätze A, B, ... abgebildet werden deutlich (und relativ) Primzahlen, und neben jedem Satz speichern Sie das Produkt aller Mitglieder als p (A), p (B) usw. dann Untergruppen und eine Obermenge können durch ob p (X) gefunden werden kehrt ein Faktor von p (Y) oder umge ist.

Sie könnten mit einigen sehr großen Zahlen am Ende ich denke, aber es funktioniert in der Theorie.

Zum Beispiel:

, wenn [a b c d] -> [2 3 5 7], P (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

Answer 4

Was für eine dorky site! Ich habe jetzt registriert, kann so zu gegebener Zeit von gestern Kommentar zu stopfen können. Bis dahin aber ...

@Stephen C: obwohl ich mein Englisch glauben angemessen zu sein scheinen ich eine explicator erworben zu haben: er Bits verpasst hat, aber, und seine Bemerkung sollte wie folgt lauten:

---

  

@Stephen C: Suche nach den Faktoren eines   willkürliche Zahl ist in der Tat NP vollständig, aber hier nicht relevant. Das   Frage ist, ob die kleinere von zwei   genau Zahlen teilt die größer ist, eine   einfacher Modul-Betrieb. Zum Beispiel,   p (bc) = 15 ein Teiler von p (abcd) = 210,   bc so eine Teilmenge von ABCD ist (wie sind Sätze abd   und abc).

     

einen neuen Satz Hinzufügen von S an die bestehende Sammlung von N-Sets ist O (N), das den Vergleich und die Aufteilung der großen Zahlen unter der Annahme, dauert ungefähr zur gleichen Zeit unabhängig von N.

     

Für jeden vorhandenen Eintrag E in der Sammlung von Sätzen, Stopp, wenn p (S)   

p (E) und p (E) teilt p (S) genau. In S, wenn Sie bis zum Ende der Sammlung bekommen. Eine Anordnung   von bignums funktionieren würde.

---

@JL:., Wenn Sie möchten meinen Vor-Ort-sein Stalker bemühen Sie bitte 1) Mehrwert 2) genau