python - 剖析 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]