Python Kombinatorik, Teil 2
Dies ist eine Follow-up-Frage zu Kombinatorik in Python
Ich habe einen Baum oder ein gerichtetes azyklisches Diagramm, wenn Sie mit einer Struktur wie folgt aussehen:
Dabei sind r Stammknoten, p sind Elternknoten, c sind Kindknoten und b sind hypothetische Zweige. Die Wurzelknoten sind nicht direkt mit den Elternknoten verbunden, es ist nur eine Referenz.
Ich bin daran interessiert, alle Kombinationen von Zweigen unter den Nebenbedingungen zu finden:
- Ein untergeordnetes Element kann von einer beliebigen Anzahl von übergeordneten Knoten gemeinsam genutzt werden, vorausgesetzt, diese übergeordneten Knoten teilen sich keinen Stammknoten.
- Eine gültige Kombination sollte keine Untermenge einer anderen Kombination sein
In diesem Beispiel sind nur zwei gültige Kombinationen unter den Einschränkungen möglich:
%Vor%Die Datenstruktur ist wie z. B. b ist eine Liste von Verzweigungsobjekten, die Eigenschaften r, c und p haben, z. B.:
%Vor%4 Antworten
Dieses Problem kann in Python einfach und elegant gelöst werden, denn es gibt ein Modul namens "itertools".
Nehmen wir an, wir haben Objekte vom Typ HypotheticalBranch, die die Attribute r, p und c haben. So wie du es in deinem Post beschrieben hast:
%Vor%Ihr Satz hypothetischer Zweige ist also
%Vor%Die magische Funktion, die eine Liste aller möglichen Zweigkombinationen zurückgibt, könnte folgendermaßen geschrieben werden:
%Vor%Um genau zu sein, gibt diese Funktion einen Iterator zurück. Holen Sie sich die Liste, indem Sie darüber iterieren. Diese vier Codezeilen werden alle möglichen Kombinationen ausdrucken:
%Vor%Die Ausgabe dieses Programms ist:
%Vor%... was genau Sie wollten.
Was macht das Skript? Es erstellt eine Liste aller hypothetischen Zweige für jede Kombination (Wurzelknoten, Kindknoten). Und dann ergibt es das Produkt dieser Listen, d. H. Alle möglichen Kombinationen eines Elements aus jeder der Listen.
Ich hoffe, ich habe bekommen, was Sie eigentlich wollten.
Die zweite Einschränkung bedeutet, dass Sie maximale Kombinationen wünschen, d. h. alle Kombinationen mit der Länge, die der größten Kombination entspricht.
Ich würde dies angehen, indem ich zuerst die "b" -Struktur durchquere und eine Struktur namens "c" erstelle, um alle Zweige zu speichern, die zu jedem Kindknoten kommen und durch den Wurzelknoten kategorisiert werden, der zu ihm kommt.
Dann, um Kombinationen für die Ausgabe zu konstruieren, können Sie für jedes Kind einen Eintrag aus jeder Wurzelmenge hinzufügen, der nicht leer ist. Die Reihenfolge (Ausführungszeit) des Algorithmus ist die Reihenfolge der Ausgabe, die die beste ist, die Sie erhalten können.
Zum Beispiel wird Ihre "c" -Struktur wie folgt aussehen:
%Vor%Für das von Ihnen bereitgestellte Beispiel:
%Vor%Es sollte ziemlich einfach sein, es mit diesem Ansatz zu programmieren. Sie müssen nur über alle Zweige "b" iterieren und die Datenstruktur für "c" füllen. Schreiben Sie dann eine kleine rekursive Funktion, die alle Elemente in "c" durchläuft.
Hier ist der Code (ich habe oben Ihre Beispieldaten eingegeben, um den Willen zu testen):
%Vor%Hier gibt es wirklich zwei Probleme: Erstens müssen Sie den Algorithmus ausarbeiten, mit dem Sie dieses Problem lösen, und zweitens müssen Sie ihn implementieren (in Python).
Algorithmus
Ich nehme an, Sie wollen eine maximale Sammlung von Zweigen; das heißt, zu dem Sie keine weiteren Zweige hinzufügen können. Wenn Sie dies nicht tun, können Sie alle Teilmengen einer maximalen Sammlung berücksichtigen.
Daher möchten wir für einen untergeordneten Knoten so viele Zweige wie möglich verwenden, wobei die Einschränkung gilt, dass keine zwei übergeordneten Knoten einen Stamm gemeinsam haben. Mit anderen Worten, von jedem Kind können Sie höchstens eine Kante in der Nachbarschaft jedes Wurzelknotens haben. Dies scheint darauf hinzudeuten, dass Sie zuerst über die Kinder, dann über die (Nachbarschaften der) Wurzelknoten und schließlich über die Kanten zwischen diesen iterieren möchten. Dieses Konzept gibt den folgenden Pseudocode:
%Vor%Code
%Vor%Das obige scheint zu funktionieren, obwohl ich es nicht getestet habe.
Für jedes Kind c, mit hypothetischen Eltern p (c), mit Wurzeln r (p (c)), wähle genau ein Elternteil p aus p (c) für jede Wurzel r in r (p (c)) (z dass r die Wurzel von p ist und b in die Kombination einbezieht, in der b p mit c verbindet (vorausgesetzt, es gibt nur einen solchen b, was bedeutet, dass es kein Multigraph ist). Die Anzahl der Kombinationen ergibt sich aus der Anzahl der Eltern, mit denen jedes Kind hypothetisch mit jeder Wurzel verbunden ist. Mit anderen Worten, die Größe der Menge der Kombinationen ist gleich dem Produkt der hypothetischen Verbindungen aller Kind-Wurzel-Paare. In Ihrem Beispiel haben alle diese Kind-Wurzel-Paare nur einen Pfad, außer r1-c2, der zwei Pfade hat, daher ist die Größe der Kombination zwei.
Dies erfüllt die Einschränkung, dass keine Kombination eine Untermenge einer anderen ist, da wir durch die Auswahl genau eines Elternteils für jede Wurzel jedes Kindes die Anzahl der Verbindungen maximieren. Das Hinzufügen einer Kante b würde dazu führen, dass sein Stamm zweimal mit seinem Kind verbunden wird, was nicht erlaubt ist. Und da wir genau eins wählen, sind alle Kombinationen genau gleich lang.
Wenn Sie diese Auswahl rekursiv implementieren, erhalten Sie die gewünschten Kombinationen.
Tags und Links python combinatorics