剖析Python中的置换算法

Question

我想弄清楚这个排列算法是怎么工作的：

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)

输出：

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

问题

原始列表是如何打印的？你知道吗

在本例中，n的长度是3。最初，i是0。代码应该跳过if语句，然后第一次迭代对列表进行变异。我们如何得到[1, 2, 3]作为第一行输出？你知道吗

Answer 1

它确实跳过了顶层的if。它进入else并在列表中迭代j。第一次迭代的i==j==0，所以交换什么也不做，然后用（[1，2，3]，1）重复。你知道吗

这个过程对那个实例重复，i==j==1。与（[1，2，3]，2）一起递归的实例是将[1, 2, 3]打印为第一行输出的实例。你知道吗

这样就清楚了吗？你知道吗

如果没有，学习如何插入有用的print语句来跟踪执行。 也许这更清楚了。你知道吗

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)

输出：

   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]