Die Erzeugung der Partitionen einer Zahl
Ich brauchte ein Algorithmus zur Generierung aller möglichen Partitionen einer positiven Zahl, und ich kam mit einem (geschrieben als Antwort), aber es ist exponentielle Zeit.
Sollte der Algorithmus gibt alle möglichen Wege, eine Zahl ausgedrückt werden kann als Summe von positiven zahlen kleiner oder gleich sich selbst. So zum Beispiel für die Anzahl 5, das Ergebnis wäre:
- 5
- 4+1
- 3+2
- 3+1+1
- 2+2+1
- 2+1+1+1
- 1+1+1+1+1
Also meine Frage ist: gibt es einen effizienteren Algorithmus?
EDIT: Frage wurde mit dem Titel "Summe der ZERLEGUNG einer Zahl", da ich nicht wirklich wusste, was dies hieß. ShreevatsaR hingewiesen , dass Sie genannt wurden "Partitionen", also bearbeitete ich die Frage, die Titel entsprechend.
Es hat einen praktischen nutzen für mich. Ich muss erzeugen aller Partitionen der Zahl N. Jede partition entspricht eine andere Verteilung, und daher auch eine andere "Berichterstattung" Wert, die ich versuche zu maximieren.
Wenn Sie auf der Suche für Sie einfach die Anzahl der Partitionen und nicht die spezielle Formel, es ist eine geschlossener form-Lösung.
Was ist, dass die geschlossene form der Lösung?
Ich fühle mich nicht wie das hinzufügen einer neuen Antwort oder Bearbeitung von mir, aber beachten Sie, dass Knuth beschreibt algorithmen zur Erzeugung aller Partitionen in Abschnitt 7.2.1.4 (Band 4A von Die Kunst der Computer-Programmierung). Einen frühen Entwurf dieses Abschnitts ist online verfügbar. (PDF, PS)
InformationsquelleAutor Can Berk Güder | 2008-12-30
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es heißt Partitionen. [Siehe auch Wikipedia: Partition (number theory).]
Die Anzahl der Partitionen p(n) wächst exponentiell, so alles, was Sie tun, zu generieren alle Partitionen muss zwangsläufig exponentielle Zeit.
Sagte, Sie können tun, besser als das, was Ihr code tut. Sehen diese, oder deren aktualisierte version in Python-Algorithmen und Datenstrukturen von David Eppstein.
Und ich sollte wahrscheinlich Bearbeiten die Frage-Titel entsprechend.
Danke für den link zu David Eppstein ' s Seite, gerade ein Interessantes surfen auf seiner Seite.
InformationsquelleAutor ShreevatsaR
Hier ist meine Lösung (exponential time) in Python:
InformationsquelleAutor Can Berk Güder
Wenn Sie Fragen zu effizienteren Algorithmus, ich weiß nicht, was zu vergleichen. Aber hier ist ein Algorithmus geschrieben geradlinig (Erlang):
Es ist exponentiell in der Zeit (wie Kann Berk Güder Lösung in Python) und linear in den Stapelspeicher. Aber mit demselben trick, memoization, können Sie erreichen große Verbesserung durch etwas Speicher sparen und weniger Exponenten. (Es ist zehn mal schneller N=50)
Trotzdem sollten Sie benchmark für Ihre Sprache und Zwecke.
InformationsquelleAutor Hynek -Pichi- Vychodil
Hier ist viel mehr umständlich Weg, es zu tun (das ist, was ich Tat, bevor ich wusste, dass der Begriff "partition", die es mir ermöglicht, zu tun, eine google-Suche):
danke @ShreevatsaR, ja, es funktioniert und nun habe ich Sie in ein vollständiges Beispiel
InformationsquelleAutor johnbasil
Hier ist eine Lösung mit paramorphisms, dass ich schrieb in Haskell.
Es ist definitiv nicht die effizienteste herum, aber ich denke, es ist sehr elegant und es ist sicher lehrreich.
InformationsquelleAutor
hier ist der java-code für diese Frage
InformationsquelleAutor Dharmendra Parmar
Anderen Java-Lösung. Es beginnt mit dem erstellen der ersten partition, die ist nur die angegebene Zahl. Dann geht es in die while-Schleife die Suche nach der letzten Zahl in der zuletzt erstellte partition größer ist, dann 1. Von dieser Zahl bewegt es sich 1 um die nächste Zahl in der Reihe. Wenn die nächste Zahl am Ende wird die gleiche wie die gefunden Zahl bewegt er sich auf den nächsten in der Reihe. Schleife Stoppt, wenn die erste Nummer der letzten erstellten partition 1. Dies funktioniert, weil zu allen Zeiten zahlen in allen Partitionen in absteigender Reihenfolge sortiert werden.
Beispiel mit der Nummer 5. Erste es schafft, die erste partition, die ist nur Nummer 5. Dann findet es die Letzte Zahl in der letzten partition, die größer als 1 ist. Seit unserem letzten partition-array [5, 0, 0, 0, 0] es gründet Nummer 5 bei index 0. Dann braucht es einen von 5 und bewegt sich zur nächsten position. Das ist, wie bekommen wir die partition [4, 1, 0, 0, 0]. Es geht in der Schleife wieder. Jetzt dauert es einen aus 4 und bewegt ihn nach oben, so erhalten wir [3, 2, 0, 0, 0]. Dann das gleiche und wir erhalten [3, 1, 1, 0, 0]. Auf der nächsten iteration erhalten wir [2, 2, 1, 0, 0]. Jetzt dauert es eine von der zweiten 2 und versucht ihn zu bewegen, index 2, wo wir 1. Es wird überspringen, um den nächsten index, da würden wir auch 2 bekommen und wir hätten partition [2, 1, 2, 0, 0] das ist Dupliziere einfach das Letzte. stattdessen bekommen wir [2, 1, 1, 1, 0]. Und im letzten Schritt erhalten wir [1, 1, 1, 1, 1] und Schleife existiert seit der ersten Nummer der neuen partition ist 1.
InformationsquelleAutor celezar
Java-Implementierung. Profitieren könnten von memoization.
InformationsquelleAutor user2429738