需要帮助让这个递归函数工作

Question

我有一个对象 person，它定义了位于 x、y 位置的人

class Person:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return "Person({}, {})".format(self.x, self.y)

    # creates a duplicate of Person at a new x, y -> x_new, y_new
    def next(self, x_movement, y_movement):
        # this is not how the actual movement is calculated, but works for demonstration
        return Person(self.x + x_movement, self.y + y_movement)

我希望为这个人找到所有可能的动作，t_steps 将来。可能的运动由一个数组限定（在任何给定时间可能不同，所以这是一个例子）。

x_possible = [-1, 0, 1] 注意：在另一个运行代码中它可能是 [3, 5, 2, 4] 所以算法需要使用这个数组了解可能的运动。

y_possible = [-1, 0, 1]

方法调用是这样的：

initial_person = Person(0, 0)
# all possible movements for person, 3 time steps into the future
all_possible_movements_for_person = get_possible_movements(initial_person , 3)

方法 get_possible_movements 必须 return 一个元组数组，其中每个元组的结构如下：

(
x_new = FIRST movement of x from this branch of movements,
y_new = FIRST movement of y from this branch of movements,
next Person from the initial_person --> person_2 = initial_person.next(x_new, y_new),
next Person from the person_2       --> person_3 =       person_2.next(x_possible[i] , y_possible[j],
.
.
will have a person count equal to t_step from the method call
)

example:
initial_person = Person(0, 0)
# all possible movements for person, 3 time steps into the future
all_possible_movements_for_person = get_possible_movements(initial_person , 3)
all_possible_movements_for_person contains a large array of tuples with first entry:

# I am showing the movements made on the person in the tuple for example
(-1, -1, person(-1,-1), person2(-1,-1), person3(-1,-1))
- first element is 1 because the algorithm should pick the first x_movement to be -1 based on the
possible movements array.
- second is -1 for the same reason with y movements.
- the first person in the array is from doing the operation initial_person.next(-1,-1)
- the second person in the array is from doing the operation person1.next(-1,-1)
- the third person in the array is from doing the operation person2.next(-1,-1)


following similar logic, the next tuple in the output array would be:
(-1, -1, person(-1,-1), person2(-1,-1), person4(-1,0))
the person 4 object is new and is the next entry in the y_movements array to get that person.
then
(-1, -1, person(-1,-1), person2(-1,-1), person5(-1,1))
(-1, -1, person(-1,-1), person2(-1,-1), person6(0,-1))
(-1, -1, person(-1,-1), person2(-1,-1), person7(0,0))

输出看起来像 example，但请记住，我使用字符串来表示此输出示例中的对象。

我的尝试在这里....它没有输出接近我需要的结果，我认为我什至不接近。我不擅长递归。

x_possible = [-1, 0, 1]
y_possible = [-1, 0, 1]


class Person:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return "Person({}, {})".format(self.x, self.y)

    # creates a duplicate of Person at a new x, y -> x_new, y_new
    def next(self, x_movement, y_movement):
        # this is not how the actual movement is calculated, but works for demonstration
        return Person(self.x + x_movement, self.y + y_movement)

def get_possible_movements(c, n):
    locs = []
    get_people_recursion(c, n, n, 0, 0, locs, ())
    return locs


def get_people_recursion(person, i, time_step, a_index, b_index, locs, tup):
    if time_step < 0:
        locs.append(tup)
        return

    if a_index >= len(x_possible) or b_index >= len(y_possible):
        return

    if time_step == i:
        tup += (x_possible[a_index], y_possible[b_index])

    c_next = person.next(x_possible[a_index], y_possible[b_index])
    tup += (c_next,)

    get_people_recursion(c_next, i, time_step-1, a_index, b_index, locs, copy.deepcopy(tup))
    get_people_recursion(c_next, i, time_step, a_index + 1, b_index, locs, copy.deepcopy(tup))

all_people = get_possible_movements(Person(0, 0), 1)
print(len(all_people))
for i in all_people:
    print(i)

此输出：

(-1, -1, Person(-1, -1), Person(-2, -2))
(-1, -1, Person(-1, -1), Person(-2, -2), Person(-2, -3))
(-1, -1, Person(-1, -1), Person(-2, -2), Person(-2, -3), Person(-1, -4))
(-1, -1, Person(-1, -1), 0, -1, Person(-1, -2), Person(-1, -3))
(-1, -1, Person(-1, -1), 0, -1, Person(-1, -2), Person(-1, -3), Person(0, -4))
(-1, -1, Person(-1, -1), 0, -1, Person(-1, -2), 1, -1, Person(0, -3), Person(1, -4))

可能有用也可能没用的图表...https://prnt.sc/sliwcx

Answer 1

您的代码已关闭。匹配字符串输出的技巧是保留一个 count 变量来构建结果字符串或一个静态 class 变量来计算 id。

除此之外，递归遍历，push/pop一个栈来存放路径。其他都是 products.

这是代码。

import itertools

class Person:
    def __init__(self, n, a, b):
        self.n = n
        self.a = a
        self.b = b

    def __repr__(self):
        return f"Person{self.n}"

def produce_c(a, b, n):
    combos = list(itertools.product(a, b))
    count = 0

    def explore(pair, path=[]):
        nonlocal count
        count += 1
        path.append(Person(count, *pair))

        if len(path) == n:
            yield tuple(path)
        else:
            for pair in combos:
                yield from explore(pair, path)

        path.pop()

    for pair in combos:
        for path in explore(pair):
            yield (*pair, *path)

if __name__ == "__main__":
    for x in produce_c([-1, 0, 1], [-1, 0, 1], 3):
        print(x)

需要帮助让这个递归函数工作

Need help getting this recursive function working

python

recursion

depth-first-search

python-3.x