I am working on a simple program where I want to traverse in a 2D-grid. I have n - particles starting from (0, 0), that is start of the grid and I want all possible coombination of positions of particles in that grid. For that I wrote a following code for find all possible combinations of positions of particles.
def transversal_method(num_particles, grid_size):
# start position of particles
p = [ (0, 0) for _ in range(num_particles)]
""" while last particle is not reached till end """
while(p[-1] != (grid_size - 1, grid_size - 1 )):P
print(p)
#if first particle reach the end of the grid
if((p[0] == (grid_size - 1 , grid_size - 1 ))):
""" updating reamining particle positions """
for i in range(1, num_particles):
if((p[i - 1] == (grid_size - 1, grid_size - 1 ))):
p[i] = tuple(update_pose(list(p[i]), grid_size))
""" updating last-particle position in reverse manner """
for i in range(num_particles - 1, -1, -1):
if(p[i - 1] == (grid_size - 1, grid_size - 1)):
p[i - 1] = p[i]
continue # takes control to the next iteration of while loop
""" updating first-particle position """
p[0] = tuple(update_pose(list(p[0]), grid_size))
The output of this, for 3 particles and grid size 5x5, looks something like this,
[(0, 0), (0, 0), (0, 0)]
[(0, 1), (0, 0), (0, 0)]
[(0, 2), (0, 0), (0, 0)]
.
.
[(5, 5), (0, 0), (0, 0)]
[(0, 1), (0, 1), (0, 0)]
[(0, 2), (0, 1), (0, 0)]
.
.
[(5, 5), (5, 5), (0, 0)]
[(0, 1), (0, 1), (0, 1)]
.
.
[(5, 5), (5, 5), (5, 5)]
you can see that, when the first particle reaches the end of the grid, it updates the second particle and the first particle position is set to the updated position of second psrticle to avoid redundant combination of positions.
For 4 particles, to reach the end of 10x10 gird, it takes approx. 38 secs, and I WOULD LIKE TO OPTIMIZE THIS CODE. Can anyone have any suggestions? Any exisiting source/implementations is there which performs the same thing which I want? Helo would be really appreciated