4X4矩阵中长度为5的数字的所有可能组合 [英] All possible combinations of numbers of length 5 in a 4X4 matrix
问题描述
我有一个矩阵
1 9 2 3
5 0 0 6
8 4 4 8
2 3 7 8
我需要找到长度5的所有可能组合。
I need to find all possible combinations of numbers of length 5.
约束：
-
从表格中的任意位置开始矩阵，您只能移动到您的下一个直接邻居，即，如果您从（0,0）开始表格，您的邻居必须是（0,1），（1,1），（1,0），如果您选择一个职位，则表格该位置，您只能移至其直接邻居，依此类推。
Starting form a any position in the matrix you can only move to your next immediate neighbor i.e if u start form say (0,0) your neighbor must be (0,1),(1,1),(1,0) and if you pick a position then form that position you can only move to its immediate neighbor and so on.
数字的长度必须为5位数字，例如，如果我从（0,0）开始，值为1，那么我可以产生序列15151或19232或10063，这样您就可以在应用了约束1的情况下按任意顺序移动。
The length of the number must be 5 digit's i.e for example if i start from (0,0) with value 1 i can produce a sequence 15151 or 19232 or 10063 so on you can move in any sequence with the constraint 1 applied.
该解决方案必须在7秒内产生输出，因此首选python，因为它是我的最爱。 ;）
The solution must produce the output in 7sec and python is preferred since its my favorite. ;)
好的，我错过了一些程序必须使用所有16个数字的东西，即它必须使用所有16个数字作为初始并产生5位数的序列。
OK i missed some things the program must use all 16 numbers i.e it must use all the 16 numbers as initial and produce the 5 digit sequence.
推荐答案
首先，您必须考虑如何从矩阵的一个位置开始，然后
First, you have to think about how to start at one position in the matrix and move to an adjacent one.
蛮力方法只是列出所有可用的单元格和每个单元格的所有相邻单元格。
The brute force method is simply to list all available cells and all adjacent cells for 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 a problem this small, this is pretty simple; however, there is always a chance of typos. Another solution is to write a 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 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)
一旦我们知道哪些单元格彼此相邻，就可以继续寻找有效路径：
Once we know which cells are next to each other, we can proceed to seek valid paths:
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
我们可以通过分析找出需要花费多长时间：
We can find out how long this takes by profiling:
import cProfile
def test():
sols = [i for i in matrix_path(5)]
print len(sols), "paths found"
cProfile.run("test()")
返回
16860找到的路径
121497函数在0.678 CPU秒内调用（16865个原始调用）
16860 paths found 121497 function calls (16865 primitive calls) in 0.678 CPU seconds
这将返回单元位置列表的列表；我们想将其转换为矩阵中的实际值，
This returns a list of lists of cell-positions; we want to turn this into the actual values from the matrix,
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)]
我们还希望将列表简化为唯一的结果：
We also want to reduce the list to unique results:
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函数调用（3372 5个原始调用）在0.845 CPU秒内
8651 unique results 138357 function calls (33725 primitive calls) in 0.845 CPU seconds
这篇关于4X4矩阵中长度为5的数字的所有可能组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
