Python列表append传入x与list(x)输出差异原因及解决方案

问题复现 #

第一段代码（append时使用list(x)） #

l="??"
ans=[]
g=list(l)
def allcombination(x):
    for i in range(len(x)):
        if x[i]=='?':
            x[i]='A'
            allcombination((x))
            ans.append(list(x))           # 问题标注行
            x[i]='B'
            allcombination((x))
            ans.append(list(x))           # 问题标注行
            return
allcombination(g)
print(ans)

运行输出：
[['A', 'A'], ['A', 'B'], ['A', 'B'], ['B', 'B']]

第二段代码（append时直接传入x） #

l="??"
ans=[]
g=list(l)
def allcombination(x):
    for i in range(len(x)):
        if x[i]=='?':
            x[i]='A'
            allcombination((x))         # 问题标注行
            ans.append((x))
            x[i]='B'
            allcombination((x))         # 问题标注行
            ans.append((x))
            return
allcombination(g)
print(ans)

运行输出：
[['B', 'B'], ['B', 'B'], ['B', 'B'], ['B', 'B']]

参考正确实现代码 #

l="??"
ans=[]
g=list(l)
def allcombination(x):
    for i in range(len(x)):
        if x[i]=='?':
            x[i]='A'
            allcombination(list(x))
            x[i]='B'
            allcombination(list(x))
            return
    ans.append(list(x))        # 直接append(x)同样会得到错误结果
allcombination(g)
print(ans)

运行输出：
[['A', 'A'], ['A', 'B'], ['B', 'A'], ['B', 'B']]

核心原理说明 #

所有结果差异的本质原因是Python中列表（list）属于可变对象，变量存储的是对象的内存引用，而非对象本身的独立拷贝，不同写法的行为逻辑如下：

• 直接append(x)的行为
  执行ans.append(x)时，存入ans列表的不是x当前值的快照，而是x指向的列表对象的内存地址。后续递归过程中对x指向的列表做任何修改（比如回溯时把位置i的字符从'A'改成'B'），都会同步反映到ans中所有指向同一个内存地址的元素上。
  第二段代码全程递归传递的都是同一个原始列表g的引用，所有递归层修改的都是同一块内存中的列表，递归全部执行完成后这个列表的最终值是['B','B']，因此ans里存储的4个指向同一列表的引用，打印出来全是['B','B']。
• append(list(x))的行为
  list(x)会创建一个全新的列表对象，把x当前的元素值拷贝到新列表中，新列表和原x指向的列表是完全独立的两个内存对象。后续对原x的修改不会影响这个新拷贝的列表，因此可以保留append执行那一刻x的状态快照。
  但第一段代码递归调用时传入的还是原x的引用，没有做拷贝，递归过程中会反复修改同一个列表，因此append得到的快照会出现重复值，缺少['B','A']的组合。
• 参考正确代码的逻辑
  递归调用时传入list(x)，相当于每进入一层递归，就为当前层创建一个独立的列表副本，各层递归修改自己的副本不会互相干扰；等递归走到没有'?'的终止条件时，再append当前列表的拷贝，就能收集到所有不重复的组合。如果终止条件处直接append(x)，存入的还是当前层列表的引用，后续当前层回溯修改值时依然会污染ans中的结果，因此必须用list(x)做拷贝。

解决方案 #

涉及递归、回溯操作修改可变对象（列表、字典、自定义类实例等）时，需要遵守两个规则：

• 如果需要保留某一时刻可变对象的状态，必须显式做浅拷贝：列表可以用list(x)、x.copy()、x[:]的方式创建独立副本，不要直接存储原对象引用。
• 如果不希望递归/函数内部的修改影响外层的原对象，传参时就要传入对象的拷贝，不要直接传原对象的引用。

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