algorithm - 任何人都可以向我解释这个排列的算法吗？

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)