Given a numpy array of integers, I want to return a random sequence in that array?

Question

I have a numpy array, and it is defined like this-

arr = np.random.randint(20, size = (10,10))

and I want to return a random sequence in that array. The output of the array could be something like

 [[ 5 19  2 12  6  3  2  3  1 18]
 [ 2 14 19 10  7  0 13  3  6 16]
 [ 9  3 14 15  0 18 19 11  0 14]
 [10 18 10  7  2 17 12 13  8  9]
 [ 2  6  8 16 13  6 13 17 10  2]
 [ 4  2 11 12 10 13 10 18 14  5]
 [11  1  0  0 19 15  8 11  7 15]
 [ 7 10  4  2  1  9 19  1 10 16]
 [ 0  1  9  5  7  1 13 18  2 10]
 [ 1 13  8  7 13 10  7  6 11  6]]

and I would want to return something like 5, 2, 9, 3, 18, 6, 2, 11 0, 4 etc. Here is what I have tried-

def path():
    paths = []
    actions = np.random.randint(4, size = 50)
    for ix,iy in np.ndindex(room.shape):
        for i in actions:
            if i == 0:
                state = room[ix - 1][iy]
                paths.append(state)
            elif i == 1:
                state = room[ix + 1][iy]
                paths.append(state)
            elif i == 2:
                state = room[ix][iy - 1]
                paths.append(state)
            elif i == 3:
                state = room[ix][iy + 1]
                paths.append(state)
        print(paths)

And this does not work.

Answer 1

For simplicity, I'll use a smaller, 3x3 array.

arr = np.random.randint(20, size = (3,3))

Write a method to generate coordinates for all possible paths through your array. I have provided an example below, but feel free to further optimize this.

def generate_all_paths(array, length):
    length = length - 1
    y_dim = len(array)
    x_dim = len(array[0])

    # Begin with every possible direction
    paths = [[(y, x)] for y in range(y_dim) for x in range(x_dim)]

    # Every possible direction
    directions = [(0, 1), (1, 0), 
                  (0, -1), (-1, 0)]

    # NOTE: I know you stated you don't care about diagonal movement,
    # but if you did you could simply use:

    # directions = [(0,1), (1,1), 
    #               (1,0), (1, -1), 
    #               (0, -1), (-1,-1), 
    #               (-1, 0), (-1, 1)]

    temp_paths = []
    # Iterate through every path and add every
    # possible next move to it.
    for i in range(length):
        # Repeat n times
        for direction in directions:
            for p in paths:
                y, x = p[-1]
                y, x = y + direction[0], x + direction[1]
                if -1 < y < y_dim and -1 < x < x_dim and (y, x) not in p:
                    temp_paths.append(p + [(y, x)])

        # Replace main path list with the temporary one and start over
        paths = deepcopy(temp_paths)
        temp_paths = []
    return paths

 

Use the random library to obtain the coordinates for a random path as shown below:

import random
random.choice(arr)

This will yield coordinates for a random path in our array of paths:

 random_path_coordinates = random.choice(generate_all_paths(arr, 4))

Plug-in the coordinates:

final_random_path = [(arr[c[0]][c[1]]) for c in random_path_coordinates]

Example of output:

# original array:
[[ 4  3 15]
 [ 2 18 13]
 [ 3  1 15]]

# coordinates for random path of length n=4:
[(1, 0), (1, 1), (2, 1), (2, 2)]

# final path:
[2, 18, 1, 15]

Answer 2

Here's a quick and dirty algorithm to accomplish what you want:

import numpy as np
import random

# set seed to allow reproducibility if you want
random.seed(12345) # this will fix the path
np.random.seed(5) # this will fix the map
arr = np.random.randint(20, size = (10,10))

# it always start at the top but you can change it to be on of the 4 borders
# top -> 0 random
# bottom -> 9 random
# left -> random 0
# right -> random 9
start_index = (0, random.randint(0,9))
path = [tuple(start_index)]

# the directions that we can move
directions = {"left": np.array([0, -1]),
              "right": np.array([0, 1]),
              "up": np.array([-1, 0]),
              "down": np.array([1, 0])}


# some functions to help in the generation of the path

def is_valid(direction, path):
    step = tuple(path[-1] + directions[direction])
    inside_boundaries = step[0] > -1 and step[0] < 10 and step[1] > -1 and step[1] < 10
    # it's need to be inside the boundaries and 
    # do not repeat an already visited place
    return inside_boundaries and step not in path

def take_step(direction, path):
    path.append(tuple(path[-1] + directions[direction]))
    
def next_step():
    return random.sample(['left', 'right', 'down', 'up'], 4)

def reach_border(path):
    # here we also dont allow it to finish in the same border that it started
    return ((0 in path[-1] or 9 in path[-1]) and 
             path[-1][0] != path[0][0] and 
             path[-1][1] != path[0][1])


while not reach_border(path):
    
    # randomize the direction and use the first one valid
    for direction in next_step():
        if is_valid(direction, path):
            take_step(direction, path)
            break
    else:
        # if none of the possible direction are possible we start over
        # this part can be optimized to only go back one step and try another direction
        # but for this size of map this lazy approach works quite fast
        start_index = (0, random.randint(0,10))
        path = [tuple(start_index)]
        
def print_path_and_values(arr, path):
    print(arr)
    for pair in path:
        print(arr[pair], end=", ")
        
print_path_and_values(arr, path)

With these seeds we get the following output:

[[ 3 14 15  6 16  9  8  4  7 16]
 [16  7 12 15 17  7 16 12 13 11]
 [ 1 15 18  9 10  9  9  1 18  7]
 [16 14  5  0 16  4 14  4  9 19]
 [ 2  4  6  9 19 19 18 17  7  4]
 [12 13 11 11  3  1  3 14  1  7]
 [16 14  9  6 15 16  5  2 13 13]
 [11  8  0 12 12  5 14 15 18  0]
 [ 7  7 16  0  8 12  5 11  5  9]
 [ 5 18  1 15  6  3 15 17  8  0]]

16, 11, 13, 12, 4, 8, 16, 7, 17, 15, 9, 10, 16, 19, 9, 11, 6, 15, 12, 8, 0, 16, 1, 

Also, another approach would be to define start and end points and add some barriers and use a path find algorithm like A* as suggested here