How to find every walk in a numpy array
Question: I'm trying to find every single "walk" of length n through an array. A walk in
this case is defined as a sequence of length n of adjacent elements
(horizontal, diagonal, or vertical) in the array so that point is repeated.
For example, a 2x2 matrix

[1 2]  
[4 8]

would have walks of length 2: (1, 2), (1, 4), (1, 8), (2, 1), (2, 4), (2, 8)
...  
walks of length 3: (1, 2, 4), (1, 2, 8), (1, 4, 2), (1, 4, 8) ... and so on

How could I implement a fast implementation of such an algorithm for small
(5x5) matrices in python/numpy, possibly using some aspect of maths that I
don't know currently?

Current slow implementation:

    
    
    from copy import deepcopy
    
    def get_walks(arr, n):
        n = n-1
        dim_y = len(arr)
        dim_x = len(arr[0])
    
        # Begin with every possibly starting location
        walks = [[(y, x)] for y in range(dim_y) for x in range(dim_x)]
    
        # Every possible direction to go in
        directions = [(0,1), (1,1), (1,0), (1, -1), (0, -1), (-1,-1), (-1, 0), (-1, 1)]
    
        temp_walks = []
        for i in range(n):
            # Go through every single current walk and add every 
            # possible next move to it, making sure to not repeat any points
            #
            # Do this n times
            for direction in directions:
                for walk in walks:
                    y, x = walk[-1]
                    y, x = y+direction[0], x+direction[1]
                    if -1 < y < dim_y and -1 < x < dim_x and (y, x) not in walk:
                        temp_walks.append(walk + [(y, x)])
    
            # Overwrite current main walks list with the temporary one and start anew
            walks = deepcopy(temp_walks)
            temp_walks = []
    
        return walks
    


Answer: I've come up with a recursive solution. Since you want to treat only small
problems, this approach can be feasible. I don't have numpy installed for
python 3, so this is only guaranteed to work for python 2 as-is (but it should
be fairly compatible). Also, I'm pretty sure my implementation is far from
optimal.

When checking my output against yours, it occured to me that I get 200 paths
for a 3x3 case, while you get 160. Looking at the paths, I think your code has
some bug, and you are the one missing paths (and not me having additional
ones). Here's my version:

    
    
    import numpy as np
    import timeit
    
    def get_walks_rec(shape,inpath,ij,n):
        # add n more steps to mypath, with dimensions shape
        # procedure: call shorter walks for allowed neighbouring sites
    
    
        mypath = inpath[:]
        mypath.append(ij)
    
        # return if this is the last point
        if n==0:
            return mypath
    
        i0 = ij[0]
        j0 = ij[1]
    
        neighbs = [(i,j) for i in (i0-1,i0,i0+1) for j in (j0-1,j0,j0+1) if 0<=i<shape[0] and 0<=j<shape[1] and (i,j)!=(i0,j0)]
        subpaths = [get_walks_rec(shape,mypath,neighb,n-1) for neighb in neighbs]
    
        # flatten out the sublists for higher levels
        if n>1:
            flatpaths = []
            map(flatpaths.extend,subpaths)
        else:
            flatpaths = subpaths
    
        return flatpaths
    
    # front-end for recursive function, called only once
    def get_walks_rec_caller(mat,n):
        # collect all the paths starting from each point of the matrix
    
        sh = mat.shape
        imat,jmat = np.meshgrid(np.arange(sh[0]),np.arange(sh[1]))
        tmppaths = [get_walks_rec(sh,[],ij,n-1) for ij in zip(imat.ravel(),jmat.ravel())]
    
        # flatten the list of lists of paths to a single list of paths
        allpaths = []
        map(allpaths.extend,tmppaths)
    
        return allpaths
    
    # input
    mat = np.random.rand(3,3)
    nmax = 3
    
    # original:
    walks_old = get_walks(mat,nmax)
    
    # new recursive:
    walks_new = get_walks_rec_caller(mat,nmax)
    
    # timing:
    number = 1000
    print(timeit.timeit('get_walks(mat,nmax)','from __main__ import get_walks,mat,nmax',number=number))
    print(timeit.timeit('get_walks_rec_caller(mat,nmax)','from __main__ import get_walks_rec_caller,mat,nmax',number=number))
    

For this 3x3 case with a max path length of 3, 1000 runs with `timeit` gives
me 1.81 seconds with yours vs 0.53 seconds with mine (and you're missing 20%
of your paths). For a 4x4 case with max length of 4, 100 runs give 2.1 seconds
(yours) vs 0.67 seconds (mine).

An example path, which is present in mine but seems to be missing from yours:

    
    
    [(0, 0), (0, 1), (0, 0)]
    

