Recursion return wrong list of lists

问题:

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)

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

This is what it should return:

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

回答1:

This is the corrected answer:

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)

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

The correction here is:

return list_of_lists + [current_path[:]]

where I add a copy by using current_path[:]

回答2:

The logic of the code is correct, the problem that you have is that you are dealing with a list which is a mutable item. This means that every variable which has a reference to the list, gets an updated list when you change it for only one variable:

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

Something like this also happens in your code when you append to the list_of_lists. Simply changing the append to this:

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

This guarantees that you start a new list every time the code ends up there, instead of appending to a list where other parts of the code have a reference to as well.

If this is a new concept for you in Python there are plenty of nice blogs which explain this in more detail than me, e.g. here

complete code:

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