In einem Projekt, an dem ich gerade arbeite, habe ich ungefähr 80% von dem umgesetzt, was ich von meinem Programm möchte, und ich bin sehr zufrieden mit den Ergebnissen.
In den restlichen 20% stehe ich vor einem Problem, das mich ein wenig verwirrt, wie man es löst. Hier ist es:
Ich habe eine Liste von Listen erstellt, die mehrere Nummern enthalten (beliebige Länge) Zum Beispiel:
%Vor%wo n bis zu 40.000 oder so erreichen könnte.
Angenommen, jedes Listenelement ist eine Menge von Zahlen (im mathematischen Sinne), was ich tun möchte, ist, alle Kombinationen von sich gegenseitig ausschließenden Mengen abzuleiten; das heißt, wie das powerset der obigen Listenelemente, aber mit allen nicht-disjoint-set-Elementen ausgeschlossen.
Um das Beispiel mit n = 4 fortzusetzen, möchte ich eine Liste mit folgenden Kombinationen erstellen:
%Vor%Ein ungültiger Fall wäre zum Beispiel die Kombination [[1, 2, 3], [3, 6, 8]], weil 3 in zwei Elementen üblich ist. Gibt es eine elegante Möglichkeit, dies zu tun? Ich wäre sehr dankbar für jedes Feedback.
Ich muss auch angeben, dass ich die powerset-Funktion nicht ausführen möchte, da die ursprüngliche Liste eine recht große Anzahl von Elementen haben könnte (wie ich sagte, n könnte bis zu 40000 gehen) und das Potset mit so vielen Elementen würde nie enden.
Die Methode, die im folgenden Programm verwendet wird, ähnelt einigen früheren Antworten beim Ausschließen von nicht disjunkten Sätzen und testet daher normalerweise nicht alle Kombinationen. Es unterscheidet sich von früheren Antworten dadurch, dass es gierig so viele Sätze wie möglich ausschließt. Dadurch kann es mehrmals schneller ausgeführt werden als die Lösung von NPE. Hier ist ein Zeitvergleich der beiden Methoden unter Verwendung von Eingabedaten mit 200, 400, ... 1000 Größen-6-Mengen mit Elementen im Bereich von 0 bis 20:
%Vor%In den obigen Daten zeigt die linke Spalte die Ausführungszeit in Sekunden an. Die Zahlenlisten zeigen, wie viele Einzel-, Doppel- oder Dreifachverbindungen aufgetreten sind. Konstanten im Programm spezifizieren Datensatzgrößen und -eigenschaften.
%Vor% Bearbeiten: In der Funktion accrue werden die Argumente (u, bset, csets) wie folgt verwendet:
• u = Liste der Mengen in der aktuellen Vereinigung von Mengen
• bset="big set" = flacher Wert von u = bereits verwendete Elemente
• csets = Kandidatenmengen = Liste der Mengen, die für eine Aufnahme in Frage kommen
Beachten Sie, dass wenn die erste Zeile von accrue durch
def accrue(csets, u=[], bset=set()):
ersetzt wird
und die siebte Zeile von
for v in accrue (ts, y, boc):
(Wenn also die Parameter neu angeordnet werden und die Standardwerte für u und bset angegeben werden), kann accrue über [accrue(listofsets)] aufgerufen werden, um eine Liste kompatibler Vereinigungen zu erstellen.
Wenn Sie den in einem Kommentar erwähnten ValueError: zero length field name in format -Fehler bei der Verwendung von Python 2.6 verwenden, versuchen Sie Folgendes:
Ähnliche Änderungen (Hinzufügen von entsprechenden Feldnummern) können in anderen Formaten im Programm erforderlich sein. Beachten Sie, dass die Neue Funktionen in 2.6 die Seite "Support for Die Methode str.format () wurde nach Python 2.6 zurückportiert. " Während nicht angegeben wird, ob Feldnamen oder Zahlen erforderlich sind, werden keine Beispiele ohne sie angezeigt. Im Gegensatz dazu funktioniert beides in 2.7.3.
Folgendes ist ein rekursiver Generator:
%Vor% Dies ist wahrscheinlich viel effizienter als die anderen Lösungen in Situationen, in denen viele Sets gemeinsame Elemente haben (natürlich muss es im schlimmsten Fall immer noch über die 2**n Elemente des Powersets iterieren) / p>
mit itertools.combinations , set.intersection und for-else loop:
Ausgabe:
%Vor%Ähnlich wie die Lösung von NPE , aber ohne Rekursion und es gibt eine Liste zurück:
%Vor%Ergebnis:
%Vor%