Как построить массив, состоящий из всех путей заданной длины в дискретном 2D-пространстве

Question

Начиная с (0,0) на плоскости, учитывая положительное целое число n, я хочу сгенерировать все пути, состоящие из n-1 шагов от (0,0). Шаг может быть либо на шаг вправо, либо на шаг вверх. Например, если n = 4, то путь будет (0,0), (1,0), (1,1), (1,2). Я сейчас использую python

Я попытался позволить некоторому параметру подсчитать количество шагов, которые я делаю, а затем использовать цикл while, чтобы ограничить количество шагов и выполнить цикл по моему начальному массиву [[[0,0]]].

def f(n):
    A=[[[0,0]]]
    s=0
    while (int(s+1)<int(n)):
        for i in A:
            i.append([i[-1][0]+1,i[-1][1]])
            A.append(i+[i[-1][0],i[-1][1]+1])
        s+=1
    return A

print f(2)

Я получаю сообщение об ошибке: 'int' объект не имеет атрибута * getitem 'в строке 8. У меня также есть ощущение, что существуют другие проблемы с приведенным выше кодом, но я не уверен, что лучший способ сделать это

Answer 1

Добро пожаловать в Stackoverflow. Эта проблема идеально подходит для рекурсивных методов. Если у вас есть путь длины N в точке P = (x, y), то вы знаете, что он образует два возможные пути длиной N + 1, один в точку (x + 1, y) и один в точку (x, y + 1).

Единственное, что вы знаете, это то, что в начальной точке есть один путь нулевой длины. Учитывая это, вы можете вычислить пути длины 1, пути длины 2 и скоро. Чтобы отделить логику генерации пути от бизнеса потребления пути я бы предложил использовать функцию генератора, позволяющую вашей логике yield a новый путь всякий раз, когда он находит. Затем вы можете перебрать этот генератор перечислять пути. Это похоже на работу:

def paths(in_path, N=1):
    if N==1:
        yield in_path
    else:
        x, y = in_path[-1]
        yield from paths(in_path+[(x+1, y)], N-1)
        yield from paths(in_path+[(x, y+1)], N-1)

for path in paths([(0, 0)], 4):
    print(path)

Я вижу вывод

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

, что, к счастью, включает в себя приведенный вами пример.