Recursion through 2D Array

user_8033003 0
Viewed 237

I am trying to recursivley navigate through a 2d array jumping to a row with the index of a coloumn in which I can find a value. 

                                 # 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

This means for the above example: There is a value in row0 at position 1. So I go to row1. I find a value at position 2 so I go to row 2. I dont find any values in row 2 so I terminate. I do this for all possible combinations and end up with following:

row0 -> row1 -> row2

row0 -> row1 -> row3

row0 -> row2

I have tried a variety of different recursive approaches, but I cant figure it out. This works for one combination (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)

It is an infinite loop and the output is 

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
...
recursion python
2 Answers

  1. The while loop statement should be:

    while index < len(sample_array_of_arrays[row]):

  2. The main issue: you never increment index:

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

  3. Another base case is required:

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

I suggest such solution. You can customize it to get desired output.

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

Output

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

dfs function can be changed to avoid additional list checking by any function. May be this will increase performance.

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)
user_29134770
Related