I have an object person which defines a person at location 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)
I desire to find all possible movements for this person, t_steps in the future. The possible movements are bounded by an array (that may be different at any given time, so this is an example).
x_possible = [-1, 0, 1] Note: during another run of code it could be [3, 5, 2, 4] so the algorithm needs to use this array to know possible movements.
y_possible = [-1, 0, 1]
the method call is like so:
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)
the method get_possible_movements must return an array of tuples where each tuple is structured like so:
(
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))
The output would look like example, but keep in mind I used strings to represent the objects in this output example.
my attempt is here.... it doesn't output near what I need it to and I don't think I am even close. I suck at recursion.
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)
output from this:
(-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))
Diagram that may or may not help... https://prnt.sc/sliwcx
Your code is close. The trick to matching your string output is to keep a single count variable to build the result strings or a static class variable to count ids.
Other than that, traverse recursively and push/pop a stack to store the path. Everything else is products.
Here's the code.
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)