I'm currently studying on DFS and created a code like the following:
>>> 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
This is the code, and when I do the following, the possible_combs returns numbers empty lists:
>>> dfs(0, N, A) # N and A defined above
>>> possible_combs
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
I thought that something was wrong with the output, so I tried printing the output when depth==N by adding print(output) in the first code:
>>> 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]
and it prints out just fine. However, I can't find the reason why the possible_combs returns those empty list values. Can anybody help me on this??
Please try:
add import copy
change line to possible_combs.append(copy.copy(output))
Python passes lists by reference, so you need to copy the current version of output before adding it to possible_combs.