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(s, i + 1)
        s[i], s[j] = s[j], s[i]  //why it swaps back?
4

2 回答 2

2

此函数将数组突变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)
于 2012-06-09T13:47:40.397 回答
0

它交换回来，因为它是 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):
        如果 i == len(s):
            印刷
        对于范围内的 j (i, len(s))：
            s[i], s[j] = s[j], s[i]
            perm(list(s), i + 1) # 传递一个副本

评论不确定为什么这被否决了。一位用户同时对该问题发表了一些评论，但随后将其删除。我认为他们错了，我想删除评论意味着他们意识到了这一点，但我不明白他们为什么不删除反对票（如果是他们的）。或者，如果这是错误的，请有人解释，以便我学习......

于 2012-06-05T14:28:01.417 回答