如何修改Python全排列代码以返回嵌套列表？求解逻辑异常

原代码逻辑拆解 #

这是用回溯法生成全排列的实现，核心逻辑如下：

• 参数a是待排列的列表，k代表当前已固定的元素位置（前k个元素已经构成排列的一部分）
• 当k == len(a)时，说明所有元素都已固定，此时的a就是一个完整的排列
• 否则，从k到列表末尾的每个元素，依次和a[k]交换位置，递归处理k+1的位置；递归结束后再交换回来（回溯操作），恢复原列表状态，继续下一轮循环

为什么输出全相同？ #

列表是Python中的可变对象，原代码里l.append(a)只是把列表a的引用添加到了l中，而非复制一个新列表。回溯过程中代码会不断修改原列表a的元素位置，最终所有递归结束后，a会回到初始状态[1,2,3]，所以l里的所有元素都是同一个列表对象的引用，自然显示全相同。

修改方案 #

只需要在添加排列时，存入列表的副本而非原引用即可，常用的复制方式有三种：

• a.copy()（Python3+支持）
• list(a)
• a[:]（切片复制）

修改后的代码（基于全局变量版本） #

l = []
def perm(a, k=0):
    if k == len(a):
        print(a)
        l.append(a.copy())  # 存入列表副本
    else:
        for i in range(k, len(a)):
            a[k], a[i] = a[i], a[k]
            perm(a, k+1)
            a[k], a[i] = a[i], a[k]

perm([1,2,3])
print(l)

此时输出为正确的全排列嵌套列表：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

更规范的版本（函数直接返回结果，无全局变量） #

def perm(a, k=0):
    result = []
    if k == len(a):
        result.append(a.copy())
    else:
        for i in range(k, len(a)):
            a[k], a[i] = a[i], a[k]
            result.extend(perm(a, k+1))
            a[k], a[i] = a[i], a[k]
    return result

print(perm([1,2,3]))

内容的提问来源于stack exchange，提问作者boom