二维数组中长度为 8 的所有可能组合

Question

我一直在尝试组合解决问题。我有一个 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)，你可以移动到八个邻居。
很快...

Answer 1

您可以将您的矩阵视为一维数组 - 无论这里如何（将行一一“放置”）。对于一维数组，您可以编写一个类似的函数（假设您应该打印组合）

f(i, n) prints all combinations of length n using elements a[i] ... a[last].

它应该跳过从 a[i] 到 a[i + k] 的一些元素（对于所有可能的 k），打印 a[k] 并制作递归调用 f(i + k + 1, n - 1)。

Answer 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

Answer 3

有很多方法可以做到这一点。仔细检查每种组合是完全合理的第一种方法。这一切都取决于您的要求。如果您的矩阵很小，并且此操作对时间不敏感，那么就没有问题。

我并不是一个真正的算法专家，但我确信有人会在我之后发布一些非常聪明的方法来做到这一点。

另外，在 Java 中 使用 CamelCase 时，方法名称应以小写字符开头。

Answer 4

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},
}

所谓长度，是指矩阵元素组合所得 8 的总和。
即，将 8 与行本身以及其他行元素相加的元素。
从第 1 行 = { {2,6}, {3,5}, } 到现在第 1 行元素和第 2 行元素，依此类推。这就是你所期待的吗？