Gibt es einen effizienten Algorithmus für die Integer-Partitionierung mit beschränkter Anzahl von Teilen?
Ich muss eine Methode erstellen, die zwei ganze Zahlen nimmt, die n und m sein müssen, und gibt an, wie viele Möglichkeiten es gibt, m positive Zahlen zu addieren, um n zu erhalten.
Zum Beispiel sollte ein Methodenaufruf wie dieser partition(6, 2) 3 zurückgeben, da 3 Möglichkeiten möglich sind. Sie sind 5 + 1 , 4 + 2 und 3 + 3 . Übrigens ist 4 + 2 dasselbe wie 2 + 4 , daher sollte die Methode sie nicht als zwei verschiedene Varianten zählen.
Kennt jemand eine Lösung für das Problem?
Aktualisiert: n und m sind nicht größer als 150.
5 Antworten
rekursiver Algorithmus
Um alle Partitionen einer Ganzzahl n mit m teilen zu zählen, ist ein rekursiver Algorithmus die offensichtliche Wahl. Für den Fall n, m durchläuft der Algorithmus jede Option k = 1, 2, 3... für den ersten Teil und für jede dieser Optionen rekursiv mit der Schreibweise n - k, m - 1 . Zum Beispiel:
Nach einigen Rekursionen ist der Punkt erreicht wo m = 2 ; dann sind die Lösungen:
Also ist die Anzahl der Lösungen für m = 2 gleich der Anzahl der Optionen für den ersten Teil.
steigende Sequenz
Um nur eindeutige Lösungen zu zählen und Duplikate zu verwerfen, sodass 2+4 und 4+2 nicht beide gezählt werden, berücksichtigen Sie nur Lösungen, bei denen die Teile eine nicht abnehmende Sequenz bilden. zum Beispiel:
In einer aufsteigenden Reihenfolge kann der Wert des ersten Teils niemals größer als n / m sein.
Rekursion mit Minimalwert 1
Um eine steigende Sequenz aufrechtzuerhalten, muss jede Rekursion den Wert des vorherigen Teils als Mindestwert für ihre Teile verwenden; zum Beispiel:
%Vor% Um zu vermeiden, dass der Minimalwert bei jeder Rekursion übergeben werden muss, wird jede Rekursion n - k, m - 1, k durch n - k - (m - 1) * (k - 1), m - 1, 1 ersetzt, die die gleiche Anzahl an Lösungen hat. Zum Beispiel:
Dies vereinfacht nicht nur den Code, sondern hilft auch, die Effizienz bei der Verwendung von Memoization zu verbessern, da Sequenzen wie 2+2+3 , 3+3+4 und 5+5+6 alle durch ihre kanonische Form 1+1+2 und eine kleinere Menge ersetzt werden Zwischenberechnungen werden öfter wiederholt.
Memoisierung
Bei der Partitionierung mit einem rekursiven Algorithmus werden viele Berechnungen mehrfach wiederholt. Und mit steigenden Werten für n und m wird die Anzahl der Rekursionen schnell groß; z.B. Um den Fall 150, 23 (unten dargestellt) zu lösen, wird der Fall 4, 2 23.703.672 Mal berechnet.
Die Anzahl der eindeutigen Berechnungen kann jedoch niemals größer als n * m sein. Durch Zwischenspeichern des Ergebnisses jeder Berechnung in einem n * m-großen Array muss nicht mehr als n * m -Kalkulation durchgeführt werden; Nachdem ein Fall einmal berechnet wurde, kann der Algorithmus den gespeicherten Wert verwenden. Dies verbessert die Effizienz des Algorithmus enorm. z.B. Ohne Memo werden 422.910.232 Rekursionen benötigt, um den Fall 150, 23 zu lösen; Mit Memoisierung werden nur 15.163 Rekursionen benötigt.
Die folgende Abbildung zeigt Cache-Lese- und Schreibvorgänge für diesen Fall. Die grauen Zellen sind unbenutzt, die weißen Zellen sind geschrieben, aber nie gelesen. Es gibt insgesamt 2042 Schreibvorgänge und 12697 Lesevorgänge.
Reduzierung der Cachegröße
Sie werden bemerken, dass die Dreiecke oben links und unten rechts nie benutzt werden; und je näher der Wert von m an n ist, desto größer werden die unbenutzten Zonen. Um diese Platzverschwendung zu vermeiden, kann das Parallelogramm zwischen diesen beiden Dreiecken um 45 ° verschoben werden, indem der Wert für n, m in n - m, m gespeichert wird. Die Cache-Größe wird somit von (n - 1) * (m - 1) auf (n - m) * (m - 1) reduziert, und der schlimmste Fall für n,m <= 150 ist nicht mehr 149 * 149 = 22201, sondern 75 * 74 = 5550, weniger als 25% der Größe.
Codebeispiel 1: ohne Memoisierung
Codebeispiel 2: schnelle Version mit Memoisierung
Diese Version, die Zwischenergebnisse zwischenspeichert, ist viel schneller als der grundlegende Algorithmus. Auch diese Javascript-Implementierung löst das Worst-Case-Szenario für n = 150 in weniger als einer Millisekunde.
(Der schlechteste Fall für n = 1000, der m = 81 ist, löst sich auf 4.01779428811641e + 29, und dieses Ergebnis wird auch fast augenblicklich zurückgegeben. Wegen der Fließkomma-Genauigkeit von Javascript ist dies der Fall natürlich kein genaues Ergebnis.)
Codebeispiel 3: schnelle Version mit Memoisierung und kleinerem Cache
Diese Version verwendet die schiefen Cache-Indizes, um die Speicheranforderungen zu reduzieren.
Sie können dynamische Programmierung verwenden. Sei f[n][m][k] die Anzahl der Partitionen von m nicht abnehmenden positiven Zahlen, so dass die Summe n und die letzte k ist. Dann könnte man leicht sehen, dass der Update-Schritt wäre:
Um f[n][m] zu erhalten, also die Anzahl aller Partitionen, unabhängig davon, welche die letzte Zahl ist, summiere am Ende nur über alle k . Die Komplexität wäre O(n^2 m) .
Da Sie wissen, wie viele Ziffern Sie verwenden sollen, glaube ich, dass Sie das tun können.
Zuerst können Sie das tun, indem Sie wiederholt Partition (n, 2) machen. Wenn Sie wollen, n = 3, m = 3 können Sie einfach Partition (n, 2), und dann für jede der Antworten tun Sie Partition (k, 2).
Beispiel:
Partition (6, 3):
Partition (6, 2):
5 + 1, 4 + 2, 3 + 3, 2 + 4, 5 + 1
Partition (5, 2):
4 + 1, 3 + 2 ...
Dann fügst du einfach alle zusammen:
(4 + 1) + 1, (3 + 2) +1, (2 + 3) +1, (1 + 4) +1, (3 + 1) +2 ...
und sortiere sie (größte Zahl zuerst).
4 + 1 + 1, 4 + 1 + 1 ...
Dann können Sie einfach alle Duplikate entfernen
Die Partition (n, 2) wird in O (n) laufen (da Sie nur eine Schleife zu n brauchen und x + (n-x) machen). Die Anzahl der Male, die Sie dies tun müssen, ist O (m) irgendeiner Art. Und das Sortieren kann in n erfolgen (da Sie wissen, dass es ganze Zahlen sind). Ich denke also, dass dies in O (n * m) läuft, was nicht gut ist, aber für Sie nützlich sein kann (wenn n oder m ziemlich klein ist).
Dieses Problem scheint Subsummenproblem
zu sein ist ein NP problem , was bedeutet, dass alle Lösungen non-deterministic sind (d. h. es ist kein effizienter Algorithmus bekannt).
Sie können jedoch einen heuristischen Ansatz ausprobieren und einige befriedigende Ergebnisse auf effizientere Weise finden.
Tags und Links algorithm java math numbers partitioning