递归函数内更新全局字典异常：列表排列存入字典时条目被篡改

我尝试生成列表元素的所有排列，并将其存入一个全局字典outp中。但运行时发现前4个排列存入字典时更新正常，存入第5个排列时，字典中第3条和第5条的内容同时被修改。以下是我的代码和运行输出，恳请协助排查问题成因。

我的代码 #

outp={}
k=0
def func(i,arr):
    global outp
    global k
    arr=arr.copy()
    for j in range(i,len(list)):
        arr[i],arr[j] = arr[j],arr[i]
        if i!=j or i==0:
            k=k+1
            print("\n\n",arr,k)
            outp[k]=arr
            print("\n",outp)
        func(i+1,arr)

list = [1,2,3,8]
func(0,list)

运行输出 #

[1, 2, 3, 8] 1

 {1: [1, 2, 3, 8]}


 [1, 2, 8, 3] 2

 {1: [1, 2, 3, 8], 2: [1, 2, 8, 3]}


 [1, 3, 2, 8] 3

 {1: [1, 2, 3, 8], 2: [1, 2, 8, 3], 3: [1, 3, 2, 8]}


 [1, 3, 8, 2] 4

 {1: [1, 2, 3, 8], 2: [1, 2, 8, 3], 3: [1, 3, 2, 8], 4: [1, 3, 8, 2]}


 [1, 8, 2, 3] 5

 {1: [1, 2, 3, 8], 2: [1, 2, 8, 3], 3: [1, 8, 2, 3], 4: [1, 3, 8, 2], 5: [1, 8, 2, 3]}

问题成因 #

核心问题在于列表是Python中的可变对象，你存入字典的是列表对象的引用，而不是列表内容的独立副本。虽然你在函数开头做了arr = arr.copy()，但这个复制后的列表会在后续的递归和循环操作中被修改（比如交换元素），而字典中保存的始终是这个列表对象的引用——当列表内容改变时，字典中所有引用该对象的条目都会同步变化。

举个具体例子：当你把第3个排列[1,3,2,8]存入字典时，outp[3]保存的是这个列表的引用；后续操作中，这个列表被修改成了[1,8,2,3]，所以字典中outp[3]的内容也跟着变成了新的列表值，和刚存入的outp[5]内容完全一致。

另外还有两个需要修正的小问题：

• 你使用了Python内置类型名称list作为变量名，这会覆盖内置的list类，可能导致后续代码出现意外错误，建议改名。
• 当前的排列生成逻辑缺少回溯步骤（交换元素后没有交换回来），这会导致生成的排列重复或遗漏，无法正确生成所有排列。

修复方案 #

1. 存入字典时保存列表副本：将outp[k] = arr改为outp[k] = arr.copy()（或outp[k] = list(arr)），这样字典中保存的是当前列表内容的独立副本，后续修改原列表不会影响字典中的条目。
2. 添加回溯步骤：在递归调用结束后，将交换的元素交换回来，确保每次循环的初始状态正确，生成完整的排列。
3. 修改变量名：避免使用内置类型名称作为变量名。

修复后的代码如下：

outp = {}
k = 0

def func(i, arr):
    global outp
    global k
    arr = arr.copy()
    n = len(arr)
    if i == n:
        # 当i等于列表长度时，说明生成了一个完整排列
        k += 1
        outp[k] = arr.copy()
        print(f"\n\n{arr} {k}")
        print(f"\n{outp}")
        return
    for j in range(i, n):
        arr[i], arr[j] = arr[j], arr[i]
        func(i + 1, arr)
        # 回溯：交换回来，恢复初始状态
        arr[i], arr[j] = arr[j], arr[i]

my_list = [1, 2, 3, 8]
func(0, my_list)

修复说明 #

• 新增了递归终止条件if i == n，确保只有当生成完整排列时才存入字典，避免重复存入中间状态。
• 添加了回溯的交换步骤，保证每次循环的列表状态正确，能生成所有24种排列。
• 存入字典时使用arr.copy()，确保每个条目都是独立的列表副本，不会被后续修改影响。

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