python - All possible combinations of numbers of length 5 in a 4X4 matrix -

i have matrix

1 9 2 3 5 0 0 6 8 4 4 8 2 3 7 8 

i need find possible combinations of numbers of length 5.

constraints:

1. starting form position in matrix can move next immediate neighbor i.e if u start form (0,0) neighbor must (0,1),(1,1),(1,0) , if pick position form position can move immediate neighbor , on.

2. the length of number must 5 digit's i.e example if start (0,0) value 1 can produce sequence 15151 or 19232 or 10063 on can move in sequence constraint 1 applied.

3. the solution must produce output in 7sec , python preferred since favorite. ;)

ok missed things program must use 16 numbers i.e must use 16 numbers initial , produce 5 digit sequence.

first, have think how start @ 1 position in matrix , move adjacent one.

the brute force method list available cells , adjacent cells each:

nextpos = {     (0,0): [(1,0), (1,1), (0,1)],     (0,1): [(0,0), (1,0), (1,1), (1,2), (0,2)],     (0,2): [(0,1), (1,1), (1,2), (1,3), (0,3)],     (0,3): [(0,2), (1,2), (1,3)],     # etc } allpos = nextpos.keys() 

for problem small, pretty simple; however, there chance of typos. solution write generator function:

def nextpos(p,w=4,h=4):     """     @param p     current position tuple (x,y)     @param w     width of matrix     @param h     height of matrix      generate matrix cells adjacent current 1     """     rel = ((-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1))      x,y = p     dx,dy in rel:         nx,ny = x+dx, y+dy         if 0<=nx<w , 0<=ny<h:             yield (nx,ny) 

once know cells next each other, can proceed seek valid paths:

def matrix_path(pathlen, startfrom=none):     """     @param pathlen    length of path return     @param startfrom  initial location      generate adjacency paths through matrix     """      # bad path length - quit gracefully     if pathlen<1:         yield []         return      # no starting point specified - start @ point     if startfrom none:         pos in allpos:             res in matrix_path(pathlen, pos):                 yield res         return      # end of path     if pathlen==1:         yield [startfrom]         return      # current point, recurse find rest of path     pos in nextpos[startfrom]:         morepath in matrix_path(pathlen-1, pos):             yield [startfrom]+morepath 

we can find out how long takes profiling:

import cprofile  def test():     sols = [i in matrix_path(5)]     print len(sols), "paths found"  cprofile.run("test()") 

which returns

16860 paths found 121497 function calls (16865 primitive calls) in 0.678 cpu seconds

this returns list of lists of cell-positions; want turn actual values matrix,

def path_vals(mx, path):     """     @param mx    matrix data     @param path  list of cell positions      return list of values list of cell positions     """      return tuple([mx[x][y] x,y in path]) 

then

mx = [     [1,9,2,3],     [5,0,0,6],     [8,4,4,8],     [2,3,7,8] ]  def test():     sols = [path_vals(mx, i) in matrix_path(5)] 

we want reduce list unique results:

def test():     usol = list(set([path_vals(mx, i) in matrix_path(5)]))     print len(usol),"unique results"  cprofile.run("test()") 

which gives us

8651 unique results 138357 function calls (33725 primitive calls) in 0.845 cpu seconds