Python 中输入数字列表的排列

Question

我应该在 Python 中编写一个程序，它将从用户那里获取数字列表，直到用户输入 0，然后打印此数字列表的所有排列。我正在编写代码，一开始似乎是正确的，但由于某种原因，我得到了奇怪的输出。

似乎列表是静态的，每次函数 returns 都会将对象添加到最新列表中。这不会像递归调用函数之前那样发生。

这是我目前的情况：

    def permutation(numberList,array,place):
        if (place==len(numberList)):
            print array
        else:
            x=0
            while (x < len(numberList)):
                array.append(numberList[x])
                permutation(numberList,array,place+1)
                x+=1

    def scanList():
        numberList=[];
        number=input()
        #keep scanning for numbers for the list
        while(number!=0):
           numberList.append(number)
           number=input()
        return numberList

permutation(scanList(),[],0)

这是输入 1 2 3 0 的输出，例如：

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

如有任何帮助，我将不胜感激。

Answer 1

Python方法是使用itertools。

from itertools import permutations
for permutation in permutations([1,2,3]):
    print(permutation)

现在你的算法出了什么问题。正如您所注意到的，该列表是静态的（不是真的，但是您每次都使用相同的列表）

一个简单的解决方法是每次都复制列表。

def permutation(numberList,array,place):
    if (place==len(numberList)):
        print array
    else:
        x=0
        while (x < len(numberList)):
            array2 = array[:] // here happens the copy
            array2.append(numberList[x])
            permutation(numberList,array2,place+1)
            x+=1

Answer 2

事实是，Python 中的列表 [] 是动态的。所以当你用 array.append(numberList[x]) 向它添加元素时，它们会永远留在那里。只需在递归调用后删除添加的元素：

def permutation(numberList,array,place):
    if (place==len(numberList)):
        print(array)
    else:
        x=0
        while (x < len(numberList)):
            array.append(numberList[x])
            permutation(numberList,array,place+1)
            array.pop()
            x+=1

这实际上是编写深度优先搜索算法的常用方法：修改结构、进行递归调用、撤消修改。你程序的结果似乎不是输入的 permutations。

Python 中输入数字列表的排列

Permutations of a list of input numbers in Python

python

recursion

permutation