在 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]

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

Accumulating results of a recursive function in python

python

recursion