递归返回错误的列表列表 [英] Recursion return wrong list of lists

问题描述

我试图解决一个问题，其中一部分是找到从(0，0)到2d数组最右点的所有路径.这是我的代码:

I try to solve a problem and one part of it is to find all paths from (0, 0) to the right most point of the 2d array. This is my code:

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应该是所有路径.但是，当我运行该程序并打印返回值时，会得到以下输出:

where x and y is current coordinate, current_path is a list of tuples of the current path, filler is index what position of the list to change and list_of_lists should be all the paths. However, when I run this program and print the return value I get this output:

 [(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)]]

所以我得到了正确的路径，但是我不知道如何将它们保存到列表列表中.有人可以帮我吗?

So I get the correct paths, but I do not know how to save them to the list of lists. Could someone help me?

这就是我调用函数的方式:

This is how I call my function:

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)]]

推荐答案

这是正确的答案:

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[:]

这篇关于递归返回错误的列表列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！