为什么我创建的自定义函数返回空值?-DFS

Question

我目前正在学习DFS，并创建了如下代码：

>>> N = 4
>>> check_list = [False]*N
>>> output = []
>>> possible_combs = []
>>> A = [1,2,3,4]
>>> def dfs(depth, N, A):
if depth == N:
possible_combs.append(output)
return 
for i in range(N):
if check_list[i]:
continue
check_list[i] = True
output.append(A[i])
dfs(depth+1, N, A)
output.pop()
check_list[i] = False

这是代码，当我执行以下操作时，possible_combs返回数字空列表：

>>> dfs(0, N, A)    # N and A defined above
>>> possible_combs
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

我认为输出有问题，所以我尝试在depth==N时通过在第一个代码中添加print(output)来打印输出：

>>> def dfs(depth, N, A):
if depth == N:
possible_combs.append(output)
print(output)
return 
for i in range(N):
if check_list[i]:
continue
check_list[i] = True
output.append(A[i])
dfs(depth+1, N, A)
output.pop()
check_list[i] = False
>>> dfs(0, N, A)
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

而且打印得很好。但是，我找不到possible_combs返回那些空列表值的原因。有人能帮我吗？？

Answer 1

请尝试：

添加import copy

将线路更改为possible_combs.append(copy.copy(output))

Python通过引用传递列表，因此在将输出添加到possible_combs之前，需要复制当前版本。

Answer 2

Stephen Mylabathula 已经解释过了。您可以使用id(输出(来了解列表实例的散列。使用这个，您可以发现在同一个列表上执行pop和append操作。

print(id(output))
140214576196336
print(id(output[:]))
140214575515360

因此，与其将列表附加到可能的输出，不如附加列表的内容或副本，即输出[：]

def dfs(depth, N, A):
if depth == N:
possible_combs.append(output[:])
#print(output)
return 
for i in range(N):
if check_list[i]:
continue
check_list[i] = True
output.append(A[i])
dfs(depth+1, N, A,)
output.pop()
check_list[i] = False
dfs(0, N, A)