Dissecting eine Permutation Algorithmus in Python

Question

Ich versuche, meinen Kopf um, wie diese Permutation Algorithmus funktioniert zu bekommen:

def perm(n, i): 
    if i == len(n) - 1: 
     print n 
    else: 
     for j in range(i, len(n)): 
      n[i], n[j] = n[j], n[i] 
      perm(n, i + 1) 
      n[i], n[j] = n[j], n[i] # swap back, for the next loop 

perm([1, 2, 3], 0) 

Ausgang:

[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[2, 3, 1] 
[3, 2, 1] 
[3, 1, 2] 

Frage

Wie kommt es, dass die ursprüngliche Liste ist die erste Linie gedruckt?

In diesem Beispiel ist die Länge n 3. Anfangs i ist 0. Der Code sollte die if Anweisung überspringen, und dann mutiert die erste Iteration die Liste. Wie erhalten wir [1, 2, 3] als erste Zeile der Ausgabe?

Answer 1

Es tut überspringen Sie die if auf der obersten Ebene. Es fällt in die else und iteriert j durch die Liste. Die erste Iteration hat i == j == 0, also macht der Tausch nichts, und Sie kehren mit ([1, 2, 3], 1) zurück.

Dieses Verfahren zum diesem Beispiel wiederholt, mit i == == 1 j, die mit wiederkehrt ([1, 2, 3], 2) Dem Beispiel ist derjenige, der [1, 2, 3] als die erste Zeile gedruckt von Ausgabe.

Ist das klar?

Wenn nicht, lesen Sie, wie Sie nützliche print Anweisungen einfügen, um die Ausführung zu verfolgen. Vielleicht macht es das deutlicher.

indent = "" 

def perm(n, i): 
    global indent 
    indent += " " 
    print indent, "ENTER", n, i 

    if i == len(n) - 1: 
     print n 
    else: 
     for j in range(i, len(n)): 
      print indent, "RECUR", i, j 
      n[i], n[j] = n[j], n[i] 
      perm(n, i + 1) 
      n[i], n[j] = n[j], n[i] # swap back, for the next loop 

    indent = indent[2:] 

perm([1, 2, 3], 0) 

Ausgang:

ENTER [1, 2, 3] 0 
    RECUR 0 0 
    ENTER [1, 2, 3] 1 
    RECUR 1 1 
     ENTER [1, 2, 3] 2 
[1, 2, 3] 
    RECUR 1 2 
     ENTER [1, 3, 2] 2 
[1, 3, 2] 
    RECUR 0 1 
    ENTER [2, 1, 3] 1 
    RECUR 1 1 
     ENTER [2, 1, 3] 2 
[2, 1, 3] 
    RECUR 1 2 
     ENTER [2, 3, 1] 2 
[2, 3, 1] 
    RECUR 0 2 
    ENTER [3, 2, 1] 1 
    RECUR 1 1 
     ENTER [3, 2, 1] 2 
[3, 2, 1] 
    RECUR 1 2 
     ENTER [3, 1, 2] 2 
[3, 1, 2]