Рекурсия через 2D Array - PullRequest
Новая
       6

Рекурсия через 2D Array

2 голосов
/ 04 апреля 2020

Я пытаюсь рекурсивно перейти по 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 есть значение. Итак, я go в строке 1. Я нахожу значение в позиции 2, поэтому я go в строке 2. Я не нахожу никаких значений в строке 2, поэтому я заканчиваю. Я делаю это для всех возможных комбинаций и получаю следующее:

row0 -> row1 -> row1 -> row2

row0 -> row1 -> row3

row0 -> row2

Я пробовал множество различных рекурсивных подходов, но я не могу понять это. Это работает для одной комбинации (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)

Это бесконечное l oop и вывод 

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

Ответы [ 2 ]

1 голос
/ 04 апреля 2020

Предлагаю такое решение. Вы можете настроить его для получения желаемого результата. 

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 Поиск в глубину .

Вывод

* Функция 1012 *

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)
1 голос
/ 04 апреля 2020

  1. Оператор while l oop должен быть: 

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