为什么递归排列后要交换数组元素？

Question

有人可以向我解释一下这个排列算法吗？我知道它会进行排列，但我不明白为什么它会起作用。

s = [1,2,3,4,5,6,7,8,9]  
def perm(s, i):
    if i == len(s):
        print s
    for j in range(i, len(s)):
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)
        s[i], s[j] = s[j], s[i]  //why it swaps back?      

Answer 1

此函数将数组

s

变异为每种可能的排列，然后打印排列并在返回时反转突变。

在每个位置

i

，它会单独保留索引小于

i

的所有条目，尝试位置

i

中的所有后续值，并使用递归来查找具有该组固定值的所有排列以及每个选择在位置

i

。 在最高索引处，没有剩余的选择，但您已经找到了其中一种排列，因此它会打印结果。

我发现在代码中有趣的地方（例如函数的开头和结尾，在本例中是在交换处）添加额外的“调试打印”有助于理解这种递归。

它当然不是最优雅的Python（一些调试打印应该提取到函数中），但是运行这个版本的代码并添加一些“调试打印”可能会很有启发。

def perm(s, i):
    print '{padding}starting perm({list}, {index})'.format(list=s, index=i, padding=' '*i)
    if i == len(s):
        print s
    for j in range(i, len(s)):
        print '{padding}swapping s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)
        print '{padding}swapping back s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
        s[i], s[j] = s[j], s[i]
    print '{padding}returning from perm({list}, {index})'.format(list=s, index=i, padding=' '*i)

Answer 2

它会交换回来，因为它是Python代码，这意味着

s

（列表）是可变的，因此在被调用函数中对其进行的更改会影响调用者中的数组。

如果它没有交换回来，那么在调用返回后数组将处于“奇怪”状态（由先前的调用留下）。

另一种不需要突变的替代方案是：

s = [1,2,3,4,5,6,7,8,9]  
def perm(s, i):
    s = list(s) # copy before mutating
    if i == len(s):
        print s
    for j in range(i, len(s)):
        s[i], s[j] = s[j], s[i]
        perm(s, i + 1)

或者，也许更清楚：

s = [1,2,3,4,5,6,7,8,9]
def perm(s, i):
   if i == len(s):
       print s
   for j in range(i, len(s)):
       s[i], s[j] = s[j], s[i]
       perm(list(s), i + 1) # pass a copy