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.

Einfach nur neugierig: ist das eine theoretische Frage (das ist OK) oder hat es einen praktischen nutzen?
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

Schreibe einen Kommentar