Python递归函数执行时列表元素丢失，求问题排查与解决

问题根源 #

Python里列表是可变对象，函数参数传递的是对象引用。你的代码中lastelementx = x.pop()会直接修改传入的列表x：

• 第一次进入循环z=0时，调用allcombs2(x, 2)，这个递归调用里又执行了x.pop()，把列表里的第二个元素也弹出了。
• 回到上层循环的z=1时，原x已经只剩1个元素（[(1,3)]），导致allcombs2(x, 1)只能生成[3]相关的组合，丢失了[4,7]的情况。

而PHP中默认是值传递，unset($x[$xsize-1])修改的是当前函数内的数组副本，不会影响上层函数的数组，所以递归过程中每个层级的数组都是独立的，不会出现元素丢失。

修复代码 #

修改allcombs2中处理最后一个元素的部分，创建列表副本再操作，避免修改原列表：

def acaddlast(listoflists, newelement, freq):
    if freq <= 0:
        return listoflists
    newlist = [newelement for _ in range(freq)]
    for z in range(len(listoflists)):
        listoflists[z] += newlist
    return listoflists

def allcombs2(x, k):
    output = []
    if len(x) == 0 or k == 0:
        return output
    if k == 1:
        return [[z[1]] for z in x]
    countofelements = sum(z[0] for z in x)
    if k > countofelements:
        return output
    if len(x) == 1:
        return acaddlast([[]], x[0][1], k)
    if k == countofelements:
        onelist = []
        for z in x:
            onelist.extend([z[1]]*z[0])
        return [onelist]
    # 关键修改：创建x的副本，避免修改原列表
    x_copy = x.copy()
    lastelementx = x_copy.pop()
    f = min(k, lastelementx[0])
    for z in range(f+1):
        output += acaddlast(allcombs2(x_copy, k-z), lastelementx[1], z)
    if lastelementx[0] >= k:
        output += acaddlast([[]], lastelementx[1], k)
    return output

output = allcombs2([(1,3), (2,4), (1,7)], 2)
print(f"{len(output)} lists\n")
print(output)

修复后输出 #

4 lists

[[3, 4], [4, 4], [3, 7], [4, 7]]

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