python - 通过二维数组递归

Question

我试图通过一个二维数组 recursivley 导航跳转到一行，其中包含我可以找到一个值的列的索引。

                                 # 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

这意味着对于上面的例子:在位置 1 的 row0 中有一个值。所以我转到 row1。我在位置 2 找到一个值，所以我转到第 2 行。我在第 2 行中没有找到任何值，所以我终止了。我对所有可能的组合都这样做，最终得到以下结果:

row0 -> row1 -> row2

row0 -> row1 -> row3

行 0 -> 行 2

我尝试了各种不同的递归方法，但我无法弄清楚。这适用于一种组合(row0 -> row1 -> row2)

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是 Depth-first search .

输出

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)