递归生成列表全排列时append结果异常，求问题原因排查

问题场景 #

递归计算列表元素全排列时，编写了如下permute函数，传入原列表x、初始排列列表p（如[0,0,0]）、存储所有排列的空列表t。执行时print(p)能输出正确排列，但将p append到t后，t的内容全部异常（错误输出见下文）。

原代码 #

def permute(x, p, last, ind, t):
    s = len(x)
    for i in range(s):
        p[ind] = x[i]
        if(ind == last):
            print(p)
            t.append(p)
        else:
            permute(x, p, last, ind+1, t)

错误输出 #

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

问题原因 #

Python中列表是可变对象，执行t.append(p)时，并没有复制当前p的内容存入t，而是把p这个列表的引用添加到了t中。后续递归过程中，代码会不断修改p的元素值，而t里所有元素都指向同一个p的引用，最终t里的所有排列都会变成最后一次修改后的p的值。

解决方法 #

将p添加到t时，传入p的副本而非原引用。创建列表副本的常用方式有三种：

• 使用p.copy()方法
• 使用list(p)类型转换
• 使用切片p[:]

修正后的代码 #

def permute(x, p, last, ind, t):
    s = len(x)
    for i in range(s):
        p[ind] = x[i]
        if(ind == last):
            print(p)
            # 添加列表副本而非原引用
            t.append(p.copy())
        else:
            permute(x, p, last, ind+1, t)

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