python - 使用递归按字典顺序生成排列

Question

我正在做项目 euler q24，但是这段生成排列的代码没有按预期工作。我不确定如何解释代码的逻辑，但它使用递归在某个索引处创建每组排列，然后移动到下一个索引。

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

您的主要缺陷是分配列表不会创建新列表，当您向下递归时，您正在更改与调用堆栈中更上层相同的列表，因此您会得到重复和奇怪的排序。
你需要:

newList = num[:]   # Create a new list

但是，您也有一些不必要的东西。 A) 你不需要 while 循环，B) 你不需要索引和弹出:

def genPermutation(num,index):
    if index == len(num)-1:
        print(num)
        return

    for i in range(index, len(num)):
        newList = num[:]
        temp = newList.pop(i)
        newList.insert(index, temp)
        genPermutation(newList, index+1)

为您提供没有重复的完整列表:

>>> 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],
 ...

但是，整个方法效率很低。与迭代方法相比，对所有这些列表创建使用递归是非常昂贵的，参见 itertools.permutation() 的实现。