Ich habe versucht, eine einfache Quizfrage zu lösen, um alle möglichen Permutationen einer Zeichenkette mit Ruby und Rekursion zu finden.
Ich habe den folgenden Ruby-Code:
%Vor%Immer wenn ich versuche, den Code mit puts permutation ("abc") zu testen bekomme ich folgende Ausgabe:
%Vor%Theoretisch sollte es ein sehr einfaches und unkompliziertes Problem sein, aber ich bin mir sicher, dass ich etwas falsch mache. Höchstwahrscheinlich ist es etwas mit den Bereichen der Schleifen. Und ich weiß, dass die Ruby-Array-Klasse eine Instanzmethode Permutation hat, um das zu tun, aber ich versuche sie zu lösen, um sie zu üben.
Bitte beachten Sie, dass die Komplexität für die aktuelle Implementierung O (N!) ist. Gibt es trotzdem eine Verbesserung der Leistung?
Um zu sehen, was die Schwierigkeit sein könnte, versuchen wir es mit einem noch einfacheren Beispiel:
%Vor% Ihr gewünschtes Ergebnis ist ["ab", "ba"] . Mal sehen, was du bekommst:
, so dass wir nicht zurückkommen, wenn
%Vor%wird ausgeführt.
Als nächstes berechnen wir:
%Vor%Beachten Sie, dass eine direktere Vorgehensweise für diese Berechnung wie folgt ist:
%Vor%oder besser String # chr ,
%Vor% Letzteres zeigt, warum chr nicht die beste Wahl für den Variablennamen ist.
Weiter
%Vor% Ich werde nun die Rückgabewerte einrücken, um zu betonen, dass wir permutation ein zweites Mal aufrufen. Das Argument permuation lautet:
Wenn wir jetzt ausführen:
%Vor% Wir geben ["b"] zurück, also (zurück zum ursprünglichen Aufruf von permutation ):
mit chr => "a" , früher berechnet. Nächstes:
Da perms nur das einzelne Element "b" enthält, vereinfachen sich die beiden for Schleifen zu:
was ist:
%Vor% Beachten Sie, dass "b"[0..0] , "b"[0..1] und "b"[0..-1] alle gleich "b"[0] sind, was nur "b" und "b"[1..-1] #=> '' ist. Deshalb, wenn i => 0 , führen wir aus:
und wenn i => 1 :
so:
%Vor%was eindeutig nicht das ist, was Sie wollen.
Was Sie tun müssen, ist, die doppelten for Schleifen zu ändern:
, das kompakter geschrieben werden könnte, indem die Methode String # eingefügt wird :
%Vor%was normalerweise so geschrieben würde:
%Vor% Beachten Sie, dass wir .dup die Zeichenfolge vor dem Senden von insert haben müssen, da insert die Zeichenfolge ändert.
Wenn Sie das so machen, brauchen Sie result = [] nicht. Sie benötigen auch nicht return result , da parms.each_with_object result zurückgibt und wenn keine return -Anweisung vorhanden ist, gibt die Methode die letzte berechnete Menge zurück. Außerdem benötigen Sie nicht die temporäre Variable perms (oder ch , falls gewünscht).
Wenn wir das zusammen machen, haben wir:
%Vor%Versuchen wir es:
%Vor%Eki, welcher bist du auf dem Bild?
Sie können Array#permutation verwenden:
UPDATE Ohne usign Array#permutation :