使用递归生成字典顺序的置换

Question

我正在做项目eulerq24，但是这个生成排列的代码片段并没有如预期的那样工作。我不知道如何解释代码的逻辑，但它使用递归在某个索引处创建每一组置换，然后转移到下一个索引。在

def genPermutation(num,index):
    if (index == (len(num)-1)):
        print(num)
    else:
        i = 0
        while i<(len(num)-index):
            newList = num
            temp = newList[index+i]
            newList.pop(index+i)
            newList.insert(index,temp)
            genPermutation(newList,index+1)
            i = i+1

a = [0,1,2,3,4,5]
genPermutation(a,0)

Answer 1

你的主要缺陷是，分配一个列表并不会创建一个新列表，当你向下递归时，你在调用堆栈中对同一个列表进行了更改，因此你得到了重复的和奇怪的顺序。
您需要：

^{1}$

不过，你也有一些不必要的东西。A） 你不需要while循环，B）你不需要索引和pop：

^{pr2}$

提供完整的列表，无重复项：

>>> a = list(range(6))
>>> genPermutation(a,0))
[[0, 1, 2, 3, 4, 5],
 [0, 1, 2, 3, 5, 4],
 [0, 1, 2, 4, 3, 5],
 [0, 1, 2, 4, 5, 3],
 [0, 1, 2, 5, 3, 4],
 [0, 1, 2, 5, 4, 3],
 [0, 1, 3, 2, 4, 5],
 [0, 1, 3, 2, 5, 4],
 ...

然而，整个方法效率很低。与迭代方法相比，在所有这些列表创建中使用递归非常昂贵，请参见^{}的实现