Partitionen von Werten in einem Fibonacci-Aufrufgraphen (Aufrufgraph ist ein Binärbaum)
Ich habe ein laufendes Projekt, das die Fibonacci-Sequenz untersucht, das ist nur ein persönliches Projekt, ich habe eine binäre tree class erstellt, die einen binären Baum des Fibonacci-Aufrufgraphen erzeugt, also für f(3) erzeuge ich den Baum:
Ich möchte eine Methode von meinem tree class get_partitions() erstellen, die den Baum durchläuft, um Partitionen von root value zu generieren. Ich betrachte hier Summanden, die sich in der Reihenfolge als verschiedene Teile unterscheiden; Für das Beispiel hier von f(3) würde die get_partitions() -Methode den Baum durchlaufen und ergeben:
Schließlich möchte ich jede Permutation von Fibonacci-Zahlen aufzählen, die die root value , in diesem Fall 3 , aufteilen, also für Partition 1 aufgezählt wäre (2,1),(1,2) , oder Partion 2 würde aufgezählt werden (2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2) usw. ...
[Edit 1] Meine Sorge ist mit Partion 4 und Partion 5 in diesem Beispiel, da das Aufzählen aller Kombinationen dieser Partitionen doppelte Partitionen ergeben würde.
Wäre es richtig, dass die Anzahl der Kombinationen für eine gegebene root value eine katalanische Zahl ergeben würde?
Mein Tree class ist:
Ich wäre dankbar für jede Hilfe bei der Erstellung der Baumklassenmethode und jeder Erleuchtung in der Mathematik zu meinem Problem.
[EDIT:] Wie ich meine Partys bekomme
Alle Partitionen müssen zu Root -Wert summieren:
Partion 1: Von Level 1 genommen (2,1)
Partion 2: Benutze den left child node Wert von root , aber nimm jetzt die Werte der Kinder der right child node von root node (1,0) , um einen Anteil von% zu erhalten. co_de%
(2,1,0) Wenn die Durchquerung von Partion 3: des right child node -Knotens erschöpft ist, gehen Sie zur nächsten Ebene von% co_de über % -Wert von root (Stufe 2), und verwenden Sie diese Kindknotenwerte als ersten Teil von partition left child node , dann nehmen Sie den root -Wert von (1,1) node (1), um einen Anteil von% co_de zu erhalten %
right child node Behalten Sie die anfänglichen Partion-Werte von der vorherigen Partion root , aber wie bei (1,1,1) nehmen Sie die Werte der untergeordneten Elemente von Partion 4: von (1,1) node Partion 2 , um a zu erhalten Anteil von right child node
root Da das linke Kind des linken Kindes der Wurzel Kinder hat, benutze diese als ersten Teil der Partie (1,0) und nimm dann den rechten Kindwert des linken Kindes von Die (1,1,1,0) (1), geben Sie einen Anteil von Partion 5: , dann nehmen Sie den rechten Kindknoten der root (1,0) , um eine letzte Teilmenge von root
(1,0,1) als Teil 5 zu erhalten, nehmen Sie den ersten Teil von Teil 5 (1) , dann wie Teil 2 und 4 den Wert der untergeordneten Knoten von rechter Knoten der Wurzel.
1 Antwort
Hier ist ein Generator, der die Art von Werten erzeugt, die Sie wollen, aber ich habe nicht versucht, eine vollständig optimierte Lösung zu finden, da Ihre Frage an einigen Stellen ein wenig verwirrend ist.
-
Sind Sie sicher, dass Sie 0 einschließen? Es ist nicht völlig willkürlich, weil die maximale Anzahl von Nullen in einer Partition die Anzahl von Einsen ist (zB [1, 0, 1, 0, 1, 0]), aber sie scheinen nichts hinzuzufügen.
-
Wie genau bestellen Sie die Partitionen? Wenn n = 3 ist und Nullen ignoriert werden, scheinen sie nach Länge geordnet zu sein, aber wenn n = 8 ist, ist [2, 2, 2, 2] vor oder nach [1, 2, 2, 3]?
-
Willst du eigentlich, dass eine Klasse das macht, oder hast du das nur als Beispiel benutzt, weil es am einfachsten schien?
Dieser Code wird alle Permutationen von Werten in der Fibonacci-Sequenz ergeben, die zu n , einschließlich n selbst, hinzugefügt werden. Es funktioniert nur, wenn n tatsächlich in der Sequenz ist (z. B. fibs(4) löst eine Ausnahme aus).
Hier ist der Code:
%Vor% Sie können Duplikate einfach mit set(tuple(sorted(i)) for i in fibs(n)) filtern und Permutationen mit itertools.permutations erstellen.
Tags und Links python combinatorics data-structures recursion fibonacci