Ich stehe vor diesem scheinbar trivialen Problem ...
Ich möchte Python verwenden, um eine Reihe von Zahlen ( "123" zum Beispiel) zu nehmen und eine Liste mit allen möglichen Ausdrücken zu erstellen, zwischen denen ein "+" oder "-" (oder gar nichts) eingefügt werden kann irgendwelche Zahlen.
Für das Beispiel "123" wäre die Liste:
Wenn die Länge der Zahlenfolge N ist, sollte die Liste 3 ^ (N-1) Zeichenfolgen enthalten.
Ich denke, das sollte rekursiv gemacht werden, aber ich muss herausfinden, wie man die drei verschiedenen Optionen (+, -, None) zurückgibt.
Ich glaube, dass der Basisfall der Funktion sein sollte:
%Vor% Hier ist eine etwas hacky, aber kurze Lösung mit itertools.product() :
Beispiel:
%Vor%Und hier ist eine rekursive Lösung:
%Vor%Ich denke, die rekursive Lösung ist in der Tat sauberer.
Es ist ein bisschen dicht, aber itertools ist dein Freund hier:
[1 + 2 + 3, 1 + 2-3, 1 + 23, 1-2 + 3, 1-2-3, 1-23, 12 +3 ', '12 -3', '123']
Die wahre Magie hier kommt von der Funktion product , die die richtige Anzahl von Kombinationen mit Ersetzung (die auch verwendet werden könnte) nimmt. Woher wissen wir, wie viele Begriffe wir brauchen? Es sieht so aus, als ob Sie nur eine Operation zwischen zwei beliebigen Werten des Ausdrucks einfügen können, also müssen wir len(expr)-1 -Werte einfügen. Es ist nützlich, die Ausgabe von:
[(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3 ), (5, 5)]
d. Wir bekommen jede Kombination, indem wir zwei Elemente aus der Liste holen, wo die Reihenfolge wichtig ist. Die letzte Druckzeile in der Antwort ist einfach der Leim, der die beiden Ausdrücke zusammenfügt, um sicherzustellen, dass der letzte Ausdruck expr[-1] am Ende angeheftet wird.
Brechen Sie es in rekursive Teilprobleme auf: Für eine Kette von Zeichenindizes 0..N (inklusive) nehmen Sie 0 und 1, generieren Sie ein Array von Lösungen für Zeichen 2..N rekursiv (lassen Sie dieses Array A sein), was zu einem anderen Array führt wo jede Kombination von 0 und 1 (zB 01, 0 + 1, usw.) jeder Lösung in A vorangestellt wird. Wenn es keine weiteren Zeichen mehr gibt, gebe einfach die Kombinationen zurück.
Beachten Sie jedoch, dass die obige Beschreibung möglicherweise O (abgründig) sowohl im Raum als auch in der Effizienz ausführt, wenn sie blind implementiert wird.