为什么我创建的自定义函数 return 为空值？ - 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 returns 数字空列表：

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

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

>>> 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 returns 那些空列表值的原因。有人可以帮我解决这个问题吗？？

Answer 1

请尝试：

添加import copy

将行更改为 possible_combs.append(copy.copy(output))

Python 通过引用传递列表，因此您需要在将输出添加到 possible_combs.

之前复制当前版本的输出

Answer 2

Stephen Mylabathula 已经解释过了。您可以使用 id(output) 来了解列表实例的哈希值。使用这个，你会发现你正在对同一个列表进行弹出和追加操作。

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

因此，不是将列表附加到 possible_outcome，而是附加内容或列表副本，即输出 [:]

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)

为什么我创建的自定义函数 return 为空值？ - DFS

Why does the custom function I created return empty values? - DFS

python

depth-first-search