通过2D阵列递归

Question

我正在尝试递归地浏览一个2d数组，该数组跳转到一行，该行具有可以在其中查找值的列的索引。考虑以下二维阵列：

# 0  1  2  3 
sample_array_of_arrays = [[0, 1, 1, 0], #row 0
[0, 0, 1, 1], #row 1
[0, 0, 0, 0], #row 2
[0, 0, 0, 0]] #row 3

这意味着对于上面的示例：第0行中的位置1处有一个值。所以我去了第1排。我在位置2找到一个值，所以我转到第2行。我在第2行找不到任何值，所以我终止。我对所有可能的组合都这样做，最终得到以下结果：

row0 -> row1 -> row2
row0 -> row1 -> row3
row0 -> row2

我尝试了各种不同的递归方法，但我搞不清楚。这适用于一个组合(第0行-第1行-第2行(

def rec_go_through_grpah(row,index):
if sum(sample_array_of_arrays[row])==0:
print("row " +str(row) + "    reached dead end")
return
else:
while index <= len(sample_array_of_arrays[row]):
current_element = sample_array_of_arrays[row][index]
if current_element==0:
rec_go_through_grpah(row, index+1)
else:
print ("row "+str(row) + "->")
rec_go_through_grpah(index,0)
if __name__=="__main__":
sample_array_of_arrays = [[0, 1, 1, 0],  # row 0
[0, 0, 1, 1],  # row 1
[0, 0, 0, 0],  # row 2
[0, 0, 0, 0]]  # row 3

rec_go_through_grpah(0,0)

这是一个无限循环，输出为

row 0->
row 1->
row 2    reached dead end
row 1->
row 2    reached dead end
row 1->
row 2    reached dead end
row 1->
row 2    reached dead end
...

Answer 1

我建议这样的解决方案。您可以自定义它以获得所需的输出。

sample_array_of_arrays = [[0, 1, 1, 0], #row 0
[0, 0, 1, 1], #row 1
[0, 0, 0, 0], #row 2
[0, 0, 0, 0]] #row 3
def dfs(l, row, s):
s += f"row {row}"
if not any(l[row]):
print(s)
return
for col, val in enumerate(l[row]):
if val:
dfs(l, col, s + " -> " )
dfs(sample_array_of_arrays, 0, '')

dfs是深度优先搜索。

输出

row 0 -> row 1 -> row 2
row 0 -> row 1 -> row 3
row 0 -> row 2

可以更改dfs功能以避免any功能进行额外的列表检查。这可能会提高性能。

def dfs(l, row, s):
s += f"row {row}"
flag = False
for col, val in enumerate(l[row]):
if val:
flag = True
dfs(l, col, s + " -> " )
if not flag:
print(s)

Answer 2

1. while循环语句应该是：

   while index < len(sample_array_of_arrays[row]):
   

2. 主要问题：你永远不会增加index:

   while index < len(sample_array_of_arrays[row]):
   if ...:
   ....
   else:
   ....
   index += 1
   

3. 需要另一个基本情况：

   if sum(sample_array_of_arrays[row])==0:
   print("row " +str(row) + "    reached dead end")
   return
   else if index >= len(sample_array_of_arrays[row]):
   print("row " +str(row) + "    reached dead end")
   return
   else:
   ....