我一直在尝试组合解决问题。我有一个 6X6 矩阵,我试图在矩阵中找到长度为 8 的所有组合。
我必须从每行、每列位置的邻居移动到邻居,我编写了一个生成组合的递归程序,但问题是它也会生成很多重复项,因此效率低下。我想知道如何消除重复计算并节省时间。
int a={{1,2,3,4,5,6},
{8,9,1,2,3,4},
{5,6,7,8,9,1},
{2,3,4,5,6,7},
{8,9,1,2,3,4},
{5,6,7,8,9,1},
}
void genSeq(int row,int col,int length,int combi)
{
if(length==8)
{
printf("%d\n",combi);
return;
}
combi = (combi * 10) + a[row][col];
if((row-1)>=0)
genSeq(row-1,col,length+1,combi);
if((col-1)>=0)
genSeq(row,col-1,length+1,combi);
if((row+1)<6)
genSeq(row+1,col,length+1,combi);
if((col+1)<6)
genSeq(row,col+1,length+1,combi);
if((row+1)<6&&(col+1)<6)
genSeq(row+1,col+1,length+1,combi);
if((row-1)>=0&&(col+1)<6)
genSeq(row-1,col+1,length+1,combi);
if((row+1)<6&&(row-1)>=0)
genSeq(row+1,col-1,length+1,combi);
if((row-1)>=0&&(col-1)>=0)
genSeq(row-1,col-1,length+1,combi);
}
我也在考虑编写一个动态程序,基本上是通过内存递归。是不是更好的选择??如果是的话,我不清楚如何在递归中实现它。我的方法真的走到了死胡同吗???
谢谢
编辑 例如结果 12121212,12121218,12121219,12121211,12121213.
限制是你必须从任何一点移动到你的邻居,你必须从矩阵中的每个位置开始,即每一行,每一列。您可以一次移动一步,即向右、向左、向上、向下和两个对角线位置。检查 if 条件。
IE
如果您在 (0,0) 中,您可以移动到 (1,0) 或 (1,1) 或 (0,1),即三个邻居。
如果你在 (2,2) 中,你可以移动到八个邻居。
等等……
最佳答案
要消除重复项,您可以将 8 位数字序列转换为 8 位整数并将它们放入哈希表中。
记忆化可能是个好主意。您可以为矩阵中的每个单元格记住可以从中实现的所有可能的长度 2-7 组合。倒退:首先为每个单元格生成所有 2 位数字序列。然后根据3位数等。
更新:Python 代码
# original matrix
lst = [
[1,2,3,4,5,6],
[8,9,1,2,3,4],
[5,6,7,8,9,1],
[2,3,4,5,6,7],
[8,9,1,2,3,4],
[5,6,7,8,9,1]]
# working matrtix; wrk[i][j] contains a set of all possible paths of length k which can end in lst[i][j]
wrk = [[set() for i in range(6)] for j in range(6)]
# for the first (0rh) iteration initialize with single step paths
for i in range(0, 6):
for j in range(0, 6):
wrk[i][j].add(lst[i][j])
# run iterations 1 through 7
for k in range(1,8):
# create new emtpy wrk matrix for the next iteration
nw = [[set() for i in range(6)] for j in range(6)]
for i in range(0, 6):
for j in range(0, 6):
# the next gen. wrk[i][j] is going to be based on the current wrk paths of its neighbors
ns = set()
if i > 0:
for p in wrk[i-1][j]:
ns.add(10**k * lst[i][j] + p)
if i < 5:
for p in wrk[i+1][j]:
ns.add(10**k * lst[i][j] + p)
if j > 0:
for p in wrk[i][j-1]:
ns.add(10**k * lst[i][j] + p)
if j < 5:
for p in wrk[i][j+1]:
ns.add(10**k * lst[i][j] + p)
nw[i][j] = ns
wrk = nw
# now build final set to eliminate duplicates
result = set()
for i in range(0, 6):
for j in range(0, 6):
result |= wrk[i][j]
print len(result)
print result
关于c++ - 二维数组中长度为 8 的所有可能组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4521706/