Рекурсия возвращает неправильный список списков

Question

Я пытаюсь решить проблему, и одна из ее частей - найти все пути от (0, 0) до самой правой точки массива 2d. Это мой код:

def route_finder_helper(x, y, current_path, filler, list_of_lists):

    current_path[filler] = (x, y)

    if x == 0 and y == 0:
        print(current_path)
        list_of_lists.append(current_path)
        return list_of_lists

    if x == 0:
        return route_finder_helper(x, y - 1, current_path, filler - 1, list_of_lists)

    if y == 0:
        return route_finder_helper(x - 1, y, current_path, filler - 1, list_of_lists)

    return route_finder_helper(x-1, y, current_path, filler - 1, list_of_lists) + \
           route_finder_helper(x, y-1, current_path, filler - 1, list_of_lists)

, где x и y - текущая координата, current_path - список кортежей текущего пути, заполнитель - индекс, какую позицию списка следует изменить, а list_of_lists - все пути. ,Однако, когда я запускаю эту программу и печатаю возвращаемое значение, я получаю следующий вывод:

 [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
 [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)]
 [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)]
 [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)]
 [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)]
 [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
 [[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]

Таким образом, я получаю правильные пути, но я не знаю, как сохранить их в списке списков. Может ли кто-нибудь мне помочь?

Вот как я называю свою функцию:

x_coordinate = coordinates[0]  
y_coordinate = coordinates[1]  
path_length = (x_coordinate + 1) + (y_coordinate + 1) - 1  
start_filling = path_length - 1  
current_path = [0] * path_length  
paths = route_finder_helper(x_coordinate, y_coordinate, current_path, 
start_filling, [])

Вот что она должна вернуть:

[[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)],[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)], [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)], [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]

Answer 1

Это исправленный ответ:

def route_finder_helper(x, y, current_path, filler, list_of_lists):

    current_path[filler] = (x, y)

    if x == 0 and y == 0:
        return list_of_lists + [current_path[:]]

    if x == 0:
        return route_finder_helper(x, y - 1, current_path, filler - 1, list_of_lists)

    if y == 0:
        return route_finder_helper(x - 1, y, current_path, filler - 1, list_of_lists)

    return route_finder_helper(x-1, y, current_path, filler - 1, list_of_lists) + \
           route_finder_helper(x, y-1, current_path, filler - 1, list_of_lists)

x_coordinate = 2
y_coordinate = 2
path_length = (x_coordinate + 1) + (y_coordinate + 1) - 1
start_filling = path_length - 1
current_path = [0] * path_length
paths = route_finder_helper(x_coordinate, y_coordinate, current_path, start_filling, [])
print(paths)

Вывод:

[[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)], 
[(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)], 
[(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)], 
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)], 
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)], 
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]

Исправление здесь:

return list_of_lists + [current_path[:]]

, где я добавляю скопируйте с помощью current_path[:]

Answer 2

Логика кода верна, проблема в том, что вы имеете дело со списком, который является изменяемым элементом. Это означает, что каждая переменная, которая имеет ссылку на список, получает обновленный список, когда вы изменяете его только для одной переменной:

a = [1, 2, 3]
b = a
a[0] = -1
print(b)
>>> [-1, 2, 3]

Нечто подобное происходит и в вашем коде, когда вы добавляете к list_of_lists. Просто измените добавление к этому:

# return list_of_lists.append(current_path)  <- old code
return list_of_lists + [current_path]  <- new code

Это гарантирует, что вы начинаете новый список каждый раз, когда код заканчивается там, вместо добавления к списку, на который есть ссылки и на другие части кода.

Если для вас это новая концепция в Python, есть множество хороших блогов, которые объясняют это более подробно, чем я, например, здесь

завершенокод:

def route_finder_helper(x, y, current_path, filler, list_of_lists):

    current_path[filler] = (x, y)

    if x == 0 and y == 0:
        return list_of_lists + [current_path]

    if x == 0:
        return route_finder_helper(x, y - 1, current_path, filler - 1, list_of_lists)

    if y == 0:
        return route_finder_helper(x - 1, y, current_path, filler - 1, list_of_lists)

    return route_finder_helper(x-1, y, current_path, filler - 1, list_of_lists) + \
           route_finder_helper(x, y-1, current_path, filler - 1, list_of_lists)

x_coordinate = 2
y_coordinate = 2
path_length = (x_coordinate + 1) + (y_coordinate + 1) - 1
start_filling = path_length - 1
current_path = [0] * path_length
paths = route_finder_helper(x_coordinate, y_coordinate, current_path, start_filling, [])
print(paths)
>>> [[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)], [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]]