Für die Zeichenfolge "ABC" berechnet das folgende Code-Snippet 5 der insgesamt 6 Permutationen. Meine Strategie bestand darin, jedes Zeichen in jeden möglichen Index des Indexes einzufügen. Aber die Funktion bekommt niemals "CBA" als mögliche Permutation. Was vermisse ich?
Obwohl Stefan und Matt einen guten Punkt bei der Verwendung des Heap-Algorithmus machen, denke ich, dass Sie eine wichtige Frage haben, warum Ihr -Code nicht funktioniert und wie Sie das debuggen würden.
In diesem Fall ist der Algorithmus einfach falsch und der beste Weg, dies zu entdecken, ist mit Bleistift und Papier IMO. Sie picken jedes Element, entfernen es aus dem Array und injizieren es an jeder möglichen Stelle. Ihr Code tut, was Sie von ihm verlangt haben. Aber es ist nicht möglich, auf diese Weise zu "CBA" zu gelangen. Sie verschieben jeweils nur ein Element, aber "CBA" hat zwei Elemente außerhalb der Reihenfolge. Wenn Sie zu ABCD erweitert würden, würden Sie viele weitere fehlende Permutationen finden (es werden nur 10 der 24 generiert).
Obwohl der Algorithmus von Heap sehr effizient ist, ist der tiefere Punkt, dass er das gesamte Array durchläuft und jedes mögliche Paar tauscht, anstatt nur ein einzelnes Element durch das Array zu bewegen. Jeder Algorithmus, den Sie auswählen, muss diese Eigenschaft haben.
Und um meinen Hut in den Ring zu werfen, würde ich Matts Implementierung auf diese Weise erweitern:
%Vor% Hier ist ein Ausdruck von Heaps (Sedgewicks?) Algorithmus in Swift. Es ist effizient, weil das Array als Verweis übergeben wird und nicht als Wert übergeben wird (obwohl das natürlich bedeutet, dass Sie darauf vorbereitet sein müssen, das Array manipulieren zu lassen). Der Austausch wird effizient durch die Verwendung der integrierten Funktion swapAt(_:_:) ausgedrückt:
Versuchen wir es:
%Vor%Ausgabe:
%Vor% Wenn Sie mit jeder Permutation nicht nur drucken wollten, ersetzen Sie print(a) durch etwas anderes. Zum Beispiel könnten Sie jede Permutation an ein Array anhängen, das Array von Zeichen zu einer Zeichenfolge kombinieren, was auch immer.
Erfinde das Rad nicht neu. Hier ist ein einfacher Port des Heap-Algorithmus .
Tags und Links ios permutation swift