Nicht rekursive Python-Permutation - Python, Algorithmus, Permutation

Versteht jemand den folgenden iterativen Algorithmus zum Erzeugen aller Permutationen einer Zahlenliste?

Ich verstehe die Logik nicht innerhalb der while len(stack) Schleife. Kann mir bitte jemand erklären, wie es funktioniert?

# Non-Recursion
@param nums: A list of Integers.
@return: A list of permutations.

def permute(self, nums):
if nums is None:
return []
nums = sorted(nums)
permutation = []
stack = [-1]
permutations = []
while len(stack):
index = stack.pop()
index += 1
while index < len(nums):
if nums[index] not in permutation:
break
index += 1
else:
if len(permutation):
permutation.pop()
continue

stack.append(index)
stack.append(-1)
permutation.append(nums[index])
if len(permutation) == len(nums):
permutations.append(list(permutation))
return permutations

Ich versuche nur den Code oben zu verstehen.

Antworten:

Wie im Kommentarabschnitt zu Ihrer Frage erwähnt, bietet das Debugging möglicherweise eine hilfreiche Möglichkeit, um zu verstehen, was der Code tut. Lassen Sie mich jedoch einen Überblick über die Funktionsweise Ihres Codes geben.

Vor allem, obwohl es keine rekursiven gibtAufrufe an die Funktion Permutieren, der Code, den Sie zur Verfügung stellen, ist effektiv rekursiv, da es nur einen eigenen Stack verwaltet, anstatt den vom Speichermanager Ihres Betriebssystems bereitgestellten zu verwenden. Insbesondere behält der Variablenstapel sozusagen die "rekursiven Daten" bei, die von einem rekursiven Aufruf an einen anderen übergeben werden. Sie könnten und sollten vielleicht jede Iteration der äußeren while - Schleife in Erwägung ziehen permutieren Funktion als rekursiver Aufruf. Wenn Sie dies tun, werden Sie sehen, dass die äußere While-Schleife "rekursiv" jede Permutation von "traverse" durchläuft Zahlen in einer Tiefe zuerst.

Wenn man das merkt, ist es ziemlich einfach herauszufinden, was jeder "rekursive Aufruf" tut. Grundsätzlich die Variable Permutation behält die aktuelle Permutation von Zahlen welches gebildet wird, während die while-Schleife fortschreitet. Variable Permutationen speichern Sie alle Permutationen von Zahlen das sind gefunden. Wie Sie vielleicht beobachten können, Permutationen werden nur aktualisiert, wenn len (Permutation) entspricht len (Anzahl) Dies kann als Basisfall der Rekursionsbeziehung betrachtet werden, die unter Verwendung eines benutzerdefinierten Stapels implementiert wird. Schließlich wählt die innere while-Schleife grundsätzlich aus, welches Element von Zahlen Hinzufügen zu der aktuellen Permutation (d. h. in Variable gespeichert Permutation) gebildet werden.

Also das ist es wirklich. Sie können herausfinden, was genau in den für die Wartung relevanten Zeilen gemacht wird Stapel Verwenden eines Debuggers, wie vorgeschlagen. Abschließend möchte ich noch einmal betonen, dass ich persönlich diese Implementierung nicht als rekursiv betrachten würde. Es kommt einfach vor, dass diese rekursive Lösung statt der vom Betriebssystem bereitgestellten Abstraktion ihren eigenen Stack behält. Um ein besseres Verständnis dafür zu vermitteln, wie eine richtige nicht-rekursive Lösung aussehen würde, können Sie den Unterschied zwischen rekursiven und iterativen Lösungen für das Problem des Findens von n beobachten^th Fibonacci-Nummer unten angegeben. Wie Sie sehen können, behält die nicht-rekursive Lösung keinen Stack bei, und anstatt das Problem in kleinere Instanzen davon aufzuteilen (Rekursion), baut es die Lösung aus kleineren Lösungen auf. (dynamische Programmierung)

def recursive_fib(n):
if n == 0:
return 0
return recursive_fib(n-1) - recursive_fib(n-2)

def iterative_fib(n):
f_0 = 0
f_1 = 1
for i in range(3, n):
f_2 = f_1 + f_0
f_0 = f_1
f_1 = f_2
return f_1

Die Antwort von @ilim ist korrekt und sollte es seindie akzeptierte Antwort, aber ich wollte nur einen weiteren Punkt hinzufügen, der nicht als Kommentar passen würde. Während ich mir vorstelle, dass Sie diesen Algorithmus als Übung studieren, sollte darauf hingewiesen werden, dass ein besserer Weg, abhängig von der Größe der Liste, möglich ist , kann für den Benutzer sein itertools"s permutations() Funktion:

print [x for x in itertools.permutations([1, 2, 3])]

Testen auf meiner Maschine mit einer Liste von 11 Artikeln (39m Permutationen) dauerte 1,7 Sekunden mit itertools.permutations(x) aber nahm 76secs mit der benutzerdefinierten Lösung oben. Beachten Sie jedoch, dass mit 12 Elementen (479m Permutationen) die itertools Die Lösung löst einen Speicherfehler aus. Wenn Sie Permutationen dieser Größe effizient generieren müssen, sollten Sie besser auf nativen Code zurückgreifen.