Permutations

Erweitere die Anordnungen Schritt für Schritt um jeweils einen Wert. Ohne Werte gibt es eine Anordnung: die leere Liste. Um den Wert 3 zur Anordnung [1, 2] hinzuzufügen, setze ihn in jede ihrer drei Lücken: [3, 1, 2], [1, 3, 2] und [1, 2, 3]. Mach das für jede Anordnung, die du hast, und aus den Anordnungen von k Werten werden die Anordnungen von k+1 Werten.

Jede Anordnung von k+1 Werten wird genau einmal erstellt: Nimm den neuesten Wert heraus, und du erhältst die Anordnung, aus der sie entstanden ist, während die Position des neuesten Werts die Lücke angibt. Die Anzahl wächst also wie 1, 2, 6, 24, und n Werte ergeben n! Anordnungen.

Sie entstehen nicht in der erforderlichen Reihenfolge. Für [1, 2, 3] ist die erste erstellte Anordnung [3, 2, 1], daher musst du zum Schluss sortieren, indem du die Positionen nacheinander vergleichst. Dieser Sortierschritt ist der aufwendige Teil: Für n! Anordnungen braucht man ungefähr n! × log(n!) Vergleiche, und bei jedem werden bis zu n Werte gelesen. Bei sechs Werten sind das ungefähr 720 × 9.5 × 6, also etwa 41.000 Lesezugriffe. Bei dieser Methode bleibt außerdem eine ganze Generation von Anordnungen im Speicher, während die nächste erstellt wird.

Fülle n Plätze von links nach rechts. Für den ersten Platz gibt es n Kandidaten, für den zweiten n-1 und so weiter; daher kommt n!. Stelle diese Entscheidungen als Baum dar: Die Wurzel ist ein leerer Pfad, jede Kante fügt einen weiteren Wert hinzu, und jedes Blatt auf Tiefe n ist eine vollständige Anordnung. Bei sortierten Werten 1, 2, 3 hat die Wurzel die Kinder [1], [2] und [3]; [1] hat die Kinder [1, 2] und [1, 3]; jedes davon hat ein Blatt.

Backtracking durchläuft diesen Baum mit einem gemeinsamen path und einem used-Flag pro Wert. An jedem Knoten durchläuft es die Werte und überspringt die bereits verwendeten. Für jeden freien Wert wählt es diesen aus (markiert ihn als verwendet und hängt ihn an), erkundet den nächsten Schritt (ruft sich eine Ebene tiefer rekursiv auf) und macht die Auswahl rückgängig (entfernt ihn und markiert ihn wieder als frei). Durch diesen Schritt wird genau der Zustand wiederhergestellt, den die Schleife zuvor hatte, sodass der nächste Wert vom selben Knoten aus ausprobiert wird. Ein Pfad der Länge n ist ein Blatt: Erstelle eine Kopie davon und kehre zurück.

Die richtige Reihenfolge ergibt sich von selbst. Die Schleife probiert zuerst den kleinsten freien Wert aus, und der Durchlauf beendet alle Anordnungen mit einem bestimmten Präfix, bevor er dieses Präfix ändert. Daher kommen alle Anordnungen, die mit 1 beginnen, vor allen, die mit 2 beginnen, und unter ihnen kommt [1, 2, ...] vor [1, 3, ...]. Das ist lexikografische Reihenfolge. Deshalb sortierst du auch nums zuerst: Die Schleife geht die Indizes der Reihe nach durch, daher müssen die Indizes nach Wert geordnet sein.

Der Baum hat ungefähr e × n! Knoten (e ist etwa 2.72), und jeder davon durchläuft eine Schleife der Länge n. Daher beträgt die Laufzeit O(n × n!), dieselbe Größenordnung wie die Größe der Antwort. Zusätzlich zur Ausgabe enthalten der Pfad, die Flags und der Aufrufstapel jeweils höchstens n Einträge.