二维数组的递归遍历

Question

我正在尝试通过一个二维数组进行递归遍历，跳转到一个行，这个行的索引是我能在某一列找到的值。考虑下面这个二维数组：

                             # 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行。在第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

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:
       ....
   

Answer 2

我建议你可以试试这个解决方案。你可以根据自己的需要进行调整，以获得想要的结果。

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)