在python中积累递归函数的结果

Question

考虑使用以下函数在列表中更改数字：

def permute(numbers, N=0):
    # base case
    if N == len(numbers):
        print numbers
        return

    for i in range(len(numbers)-N):

        # swapping relevant elements
        element=numbers.pop(N+i)
        numbers.insert(N,element)

        # recursive call
        permute(numbers, N+1)

        # swapping back relevant elements when backtracking
        element=numbers.pop(N)
        numbers.insert(N+i,element)


numbers=[1,2,3]
permute(numbers)

为什么当我运行上面的代码时，它会产生正确的输出：

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

但是当我试图把结果累积到一个列表中时：

def permute(numbers, permutations, N=0):
    # base case
    if N == len(numbers):
        print numbers
        permutations.append(numbers)
        return

    for i in range(len(numbers)-N):

        # swapping relevant elements
        element=numbers.pop(N+i)
        numbers.insert(N,element)

        # recursive call
        permute(numbers, permutations, N+1)

        # swapping back relevant elements when backtracking
        element=numbers.pop(N)
        numbers.insert(N+i,element)


numbers=[1,2,3]
permutations=[]
permute(numbers, permutations)

print "-----------"
for p in permutations:
    print p

产出如下：

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

和我想象的不太一样..。

Answer 1

添加到permutations中的所有项实际上都是相同的列表。改变一个会改变所有其他的。最简单的解决方法是在添加列表之前先复制一份列表，因此对numbers的未来更改对已经追加的结果没有任何影响。

def permute(numbers, permutations, N=0):
    # base case
    if N == len(numbers):
        print numbers
        permutations.append(numbers[:])
        return

结果：

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