Wie würden Sie alle möglichen Kombinationen von Additionen aus einem bestimmten Satz N
von Zahlen testen, damit sie sich zu einer bestimmten endgültigen Zahl addieren?
Ein kurzes Beispiel:
- Satz von Zahlen zum Hinzufügen:
N = {1,5,22,15,0,...}
- Erwünschtes Ergebnis:
12345
Antworten:
Dieses Problem kann durch eine rekursive Kombination aller möglichen Summen gelöst werden, die diejenigen herausfiltern, die das Ziel erreichen. Hier ist der Algorithmus in Python:
Diese Art von Algorithmen wird in der folgenden Vorlesung über abstrakte Programmierung von Standford sehr gut erläutert. Dieses Video ist sehr empfehlenswert, um zu verstehen, wie Rekursion funktioniert, um Permutationen von Lösungen zu generieren.
Bearbeiten
Das obige als Generatorfunktion, was es ein bisschen nützlicher macht. Benötigt Python 3.3+ wegen
yield from
.Hier ist die Java-Version desselben Algorithmus:
Es ist genau die gleiche Heuristik. Mein Java ist ein bisschen verrostet, aber ich denke, es ist leicht zu verstehen.
C # -Konvertierung der Java-Lösung: (von @JeremyThompson)
Ruby-Lösung: (von @emaillenin)
Bearbeiten: Komplexitätsdiskussion
Wie andere erwähnen, ist dies ein NP-hartes Problem . Es kann in der Exponentialzeit O (2 ^ n) gelöst werden, zum Beispiel für n = 10 gibt es 1024 mögliche Lösungen. Wenn sich die Ziele, die Sie erreichen möchten, in einem niedrigen Bereich befinden, funktioniert dieser Algorithmus. Also zum Beispiel:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000)
generiert 1024 Zweige, da das Ziel mögliche Lösungen nie herausfiltern kann.Auf der anderen Seite werden
subset_sum([1,2,3,4,5,6,7,8,9,10],10)
nur 175 Zweige generiert, da das Ziel zu erreichen ist10
viele Kombinationen herausfiltern kann.Wenn
N
undTarget
sind große Zahlen, sollte man in eine ungefähre Version der Lösung übergehen.quelle
[1, 2, 0, 6, -3, 3], 3
- es wird nur[1,2], [0,3], [3]
[6, -3, 3]
[1, 2, 5], 5
nur Ausgänge[5]
, wenn[1, 1, 1, 1, 1]
,[2, 2, 1]
und[2, 1, 1, 1]
sind Lösungen.i+1
inremaining = numbers[i+1:]
. Es sieht so aus, als ob dieser Algorithmus keine Duplikate zulässt.[1, 1, 3]
erhalten, werfen Sie einen Blick auf stackoverflow.com/a/34971783/3684296 (Python)Die Lösung dieses Problems wurde im Internet millionenfach gegeben. Das Problem heißt Das Münzwechselproblem . Lösungen finden Sie unter http://rosettacode.org/wiki/Count_the_coins und ein mathematisches Modell davon unter http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (oder bei Google Coin Change) Problem ).
Interessant ist übrigens die Scala-Lösung von Tsagadai. In diesem Beispiel wird entweder 1 oder 0 erzeugt. Als Nebeneffekt werden alle möglichen Lösungen auf der Konsole aufgelistet. Es zeigt die Lösung an, macht sie jedoch in keiner Weise verwendbar.
Um so nützlich wie möglich zu sein, sollte der Code a zurückgeben
List[List[Int]]
, damit die Anzahl der Lösungen (Länge der Liste der Listen), die "beste" Lösung (die kürzeste Liste) oder alle möglichen Lösungen ermittelt werden können.Hier ist ein Beispiel. Es ist sehr ineffizient, aber leicht zu verstehen.
Beim Ausführen wird Folgendes angezeigt:
Das
sumCombinations()
Funktion kann für sich allein verwendet werden, und das Ergebnis kann weiter analysiert werden, um die "beste" Lösung (die kürzeste Liste) oder die Anzahl der Lösungen (die Anzahl der Listen) anzuzeigen.Beachten Sie, dass die Anforderungen auch dann möglicherweise nicht vollständig erfüllt sind. Es kann vorkommen, dass die Reihenfolge jeder Liste in der Lösung von Bedeutung ist. In einem solchen Fall müsste jede Liste so oft dupliziert werden, wie es eine Kombination ihrer Elemente gibt. Oder wir interessieren uns nur für die Kombinationen, die unterschiedlich sind.
Zum Beispiel könnten wir in Betracht ziehen,
List(5, 10)
dass dies zwei Kombinationen ergeben sollte:List(5, 10)
undList(10, 5)
. DennList(5, 5, 5)
je nach Anforderung können drei oder nur eine Kombination angegeben werden. Für ganze Zahlen sind die drei Permutationen äquivalent, aber wenn es sich um Münzen handelt, wie im "Münzwechselproblem", sind sie es nicht.Ebenfalls nicht in den Anforderungen angegeben ist die Frage, ob jede Zahl (oder Münze) nur einmal oder mehrmals verwendet werden darf. Wir könnten (und sollten!) Das Problem auf eine Liste von Vorkommenslisten jeder Zahl verallgemeinern. Dies führt im wirklichen Leben dazu, dass "mit einem Satz Münzen (und nicht mit einem Satz Münzwerte) ein bestimmter Geldbetrag verdient werden kann". Das ursprüngliche Problem ist nur ein besonderer Fall in diesem Fall, in dem jede Münze so oft vorkommt, wie erforderlich ist, um den Gesamtbetrag mit jedem einzelnen Münzwert zu ermitteln.
quelle
Im Haskell :
Und J :
Wie Sie vielleicht bemerken, verfolgen beide den gleichen Ansatz und teilen das Problem in zwei Teile: Generieren Sie jedes Mitglied des Potenzsatzes und überprüfen Sie die Summe jedes Mitglieds zum Ziel.
Es gibt andere Lösungen, aber dies ist die einfachste.
Benötigen Sie Hilfe bei einem oder bei der Suche nach einem anderen Ansatz?
quelle
not in scope: 'subsequences'
irgendwelche Zeiger?import Data.List
Eine Javascript-Version:
quelle
remaining = numbers.slice();
remaining.slice(i + 1);
sonstnumbers.slice(i + 1);
das Zahlenarrayslice
Gibt eine (flache) Kopie zurück, dasnumbers
Array wird nicht geändert .C ++ - Version desselben Algorithmus
quelle
C # -Version der @ msalvadores-Code-Antwort
quelle
Ich dachte, ich würde eine Antwort auf diese Frage verwenden, konnte es aber nicht. Hier ist meine Antwort. Es wird eine modifizierte Version einer Antwort in Struktur und Interpretation von Computerprogrammen verwendet . Ich denke, dies ist eine bessere rekursive Lösung und sollte den Puristen mehr gefallen.
Meine Antwort ist in Scala (und ich entschuldige mich, wenn meine Scala scheiße ist, ich habe gerade angefangen, sie zu lernen). Die Verrücktheit von findSumCombinations besteht darin, die ursprüngliche Liste für die Rekursion zu sortieren und eindeutig zu machen, um Dupes zu verhindern.
Um es zu benutzen:
quelle
Ich habe oben Logik von Python zu PHP konvertiert.
quelle
Eine andere Python-Lösung wäre, das
itertools.combinations
Modul wie folgt zu verwenden:Ausgabe:
[(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]
quelle
Hier ist eine Lösung in R.
quelle
subset_sum(numbers = c(1:2), target = 5)
zurück"sum(1+2+2)=5"
. Die Kombination 1 + 1 + 1 + 1 + 1 fehlt jedoch. Beim Setzen von Zielen auf höhere Zahlen (z. B. 20) fehlen noch mehr Kombinationen.subset_sum(1:2, 4)
sollte keine Lösungen zurückgeben, da es keine Kombination von 1 und 2 gibt, die zu 4 addiert. Was zu meiner Funktion hinzugefügt werden muss, ist ein Escape, wenni
es größer als die Länge vonnumbers
Hier ist eine Java-Version, die sich gut für kleine N und sehr große Zielsummen eignet, wenn die Komplexität
O(t*N)
(die dynamische Lösung) größer ist als der Exponentialalgorithmus. Meine Version verwendet ein Meet-in-the-Middle-Attacke sowie ein wenig Shifting, um die Komplexität von klassisch naivO(n*2^n)
auf klassisch zu reduzierenO(2^(n/2))
.Wenn Sie dies für Sätze mit 32 bis 64 Elementen verwenden möchten, sollten Sie
int
die aktuelle Teilmenge in der Schrittfunktion in a ändern ,long
obwohl die Leistung mit zunehmender Satzgröße offensichtlich drastisch abnimmt. Wenn Sie dies für eine Menge mit einer ungeraden Anzahl von Elementen verwenden möchten, sollten Sie der Menge eine 0 hinzufügen, um sie gerade zu nummerieren.quelle
Dies ähnelt einem Münzwechselproblem
quelle
Sehr effizienter Algorithmus mit Tabellen, die ich vor ein paar Jahren in C ++ geschrieben habe.
Wenn Sie DRUCKEN 1 einstellen, werden alle Kombinationen gedruckt (es wird jedoch nicht die effiziente Methode verwendet).
Es ist so effizient, dass es mehr als 10 ^ 14 Kombinationen in weniger als 10 ms berechnet.
quelle
Excel VBA-Version unten. Ich musste dies in VBA implementieren (nicht meine Präferenz, beurteilen Sie mich nicht!) Und verwendete die Antworten auf dieser Seite für den Ansatz. Ich lade hoch, falls andere auch eine VBA-Version benötigen.
Die Ausgabe (in das Direktfenster geschrieben) sollte sein:
quelle
Hier ist eine bessere Version mit besserer Ausgabeformatierung und C ++ 11-Funktionen:
quelle
Nicht rekursive Java -Version, die einfach immer wieder Elemente hinzufügt und diese auf mögliche Werte verteilt.
0
werden ignoriert und funktionieren für feste Listen (was Sie erhalten, ist das, womit Sie spielen können) oder eine Liste wiederholbarer Zahlen.Beispieleingabe:
Beispielausgabe:
quelle
Um die Kombinationen mit Excel zu finden - (es ist ziemlich einfach). (Ihr Computer darf nicht zu langsam sein)
Laden Sie die Excel-Datei "Sum to Target" herunter.
Folgen Sie den Anweisungen auf der Website-Seite.
hoffe das hilft.
quelle
Swift 3-Konvertierung der Java-Lösung: (von @JeremyThompson)
Verwendung:
quelle
Hiermit können auch alle Antworten gedruckt werden
Die Zeitkomplexität ist exponentiell. Reihenfolge von 2 ^ n
quelle
Ich habe etwas Ähnliches für eine Scala-Aufgabe gemacht. Ich wollte meine Lösung hier veröffentlichen:
quelle
Ich habe das C # -Beispiel auf Objective-c portiert und es in den Antworten nicht gesehen:
quelle
@ KeithBellers Antwort mit leicht geänderten Variablennamen und einigen Kommentaren.
quelle
PHP-Version , inspiriert von Keith Bellers C # -Version.
Die PHP-Version von bala funktionierte bei mir nicht, da ich keine Nummern gruppieren musste. Ich wollte eine einfachere Implementierung mit einem Zielwert und einem Zahlenpool. Diese Funktion beschneidet auch doppelte Einträge.
quelle
Als Antwort empfohlen:
Hier ist eine Lösung mit es2015- Generatoren :
Die Verwendung von Generatoren kann tatsächlich sehr nützlich sein, da Sie die Skriptausführung sofort anhalten können, wenn Sie eine gültige Teilmenge gefunden haben. Dies steht im Gegensatz zu Lösungen ohne Generatoren (dh ohne Status), die jede einzelne Teilmenge von durchlaufen müssen
numbers
quelle
Ziehen Sie zunächst 0 ab. Null ist eine Identität für die Addition, daher ist sie in diesem speziellen Fall nach den Monoidgesetzen nutzlos. Leiten Sie auch negative Zahlen ab, wenn Sie auf eine positive Zahl aufsteigen möchten. Andernfalls benötigen Sie auch eine Subtraktionsoperation.
Also ... der schnellste Algorithmus, den Sie für diesen bestimmten Job erhalten können, ist der folgende in JS.
Dies ist ein sehr schneller Algorithmus, aber wenn Sie das
data
Array absteigend sortieren , wird es noch schneller. Die Verwendung.sort()
ist unbedeutend, da der Algorithmus viel weniger rekursive Aufrufe enthält.quelle
Perl-Version (der führenden Antwort):
Ergebnis:
Javascript-Version:
Javascript-Einzeiler, der tatsächlich Ergebnisse zurückgibt (anstatt sie zu drucken):
Und mein Lieblings-Einzeiler mit Rückruf:
quelle
Dies ist eine dynamische Lösung für JS, um festzustellen, auf wie viele Arten jemand die bestimmte Summe erhalten kann. Dies kann die richtige Lösung sein, wenn Sie über die Komplexität von Zeit und Raum nachdenken.
quelle
quelle
Die Javascript-Lösung hat mir nicht gefallen. Ich habe gesehen, warum ich eine für mich selbst erstellt habe, indem ich sie teilweise angewendet, geschlossen und rekursiv gemacht habe:
Ok, ich war hauptsächlich besorgt darüber, ob das Kombinationsarray das Anforderungsziel erfüllen könnte, aber mit diesem Ansatz können Sie beginnen, den Rest der Kombinationen zu finden
Hier setzen Sie einfach das Ziel und übergeben das Kombinationsarray.
die aktuelle Implementierung, die ich mir ausgedacht habe
quelle