Во-первых, вы должны подумать о том, как начать с одной позиции в матрице и перейти к соседней.
Метод грубой силы состоит в том, чтобы просто перечислить все доступные ячейки и все соседние ячейки для каждой:
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()
Для такой маленькой проблемы это довольно просто;Однако всегда есть вероятность опечаток.Другое решение - написать функцию генератора:
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 all matrix cells adjacent to the current one
"""
rel = ((-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1))
x,y = p
for dx,dy in rel:
nx,ny = x+dx, y+dy
if 0<=nx<w and 0<=ny<h:
yield (nx,ny)
Как только мы узнаем, какие ячейки находятся рядом друг с другом, мы можем приступить к поиску действительных путей:
def matrix_path(pathLen, startFrom=None):
"""
@param pathLen Length of path to return
@param startFrom Initial location
Generate all adjacency paths through the matrix
"""
# bad path length - quit gracefully
if pathLen<1:
yield []
return
# no starting point specified - start at any point
if startFrom is None:
for pos in allpos:
for res in matrix_path(pathLen, pos):
yield res
return
# end of path
if pathLen==1:
yield [startFrom]
return
# from current point, recurse to find rest of path
for pos in nextpos[startFrom]:
for morePath in matrix_path(pathLen-1, pos):
yield [startFrom]+morePath
Мы можем выяснитьсколько времени занимает профилирование:
import cProfile
def test():
sols = [i for i in matrix_path(5)]
print len(sols), "paths found"
cProfile.run("test()")
, которое возвращает
16860 найденных путей 121497 вызовов функций (16865 примитивных вызовов) за 0,678 секунд ЦП
Возвращает список списков позиций ячеек;мы хотим преобразовать это в фактические значения из матрицы,
def path_vals(mx, path):
"""
@param mx Matrix data
@param path List of cell positions
Return list of values from list of cell positions
"""
return tuple([mx[x][y] for x,y in path])
Затем
mx = [
[1,9,2,3],
[5,0,0,6],
[8,4,4,8],
[2,3,7,8]
]
def test():
sols = [path_vals(mx, i) for i in matrix_path(5)]
Мы также хотим сократить список до уникальных результатов:
def test():
usol = list(set([path_vals(mx, i) for i in matrix_path(5)]))
print len(usol),"unique results"
cProfile.run("test()")
, что дает нам
8651 уникальных результатов 138357 вызовов функций (33725 примитивных вызовов) за 0,845 секунды ЦП