c# - 查找具有条件的所有可能二进制组合的算法

Question

这里有一个是为你的数学头脑准备的。我有一个矩阵，实际上是它的一半矩阵，沿对角线切割。矩阵的每个元素可以是 1 或 0。我需要为任何宽度 N 的矩阵找到 1 和 0 的所有可能组合。

这很简单，您可以在给定宽度 N 的情况下使用 获取此矩阵中的元素数对于这个 N=7 的例子，这会给我们 28 或元素的数量。然后你可以得到与 的组合.

所以公式是得到所有可能的组合。

这就是它变得棘手的地方。每个结果都必须满足一个条件。矩阵上每组元素的总和(如下所示，每行表示)对于第一组(第一行中的那个)必须小于 4，对于所有其他组小于 3(这些都是常数，无论N 值)。

下面是这个例子 (N=7) 的集合的样子。如果您注意到每一行都有代表。因此，对于第一组，如果组合是 0 1 0 1 0 1 0，这将是有效的，因为它的总和 < 4(从第一行开始)。对于第二组，如果组合是 1 0 0 0 0 1 0 它是有效的，因为它需要 < 3。

我需要对巨大的矩阵执行此操作，因此强制所有可能的排列以找到符合这种条件的排列是不可行的。我需要找到某种可以用来自下而上而不是自上而下生成有效矩阵的算法。也许执行单独的操作，稍后可以组合这些操作以产生一组完整的结果。

欢迎提出任何想法。

Answer 1

递归生成每个解决方案的简单算法:

global File //A file where you will store your data
global N    //Your matrix size

//matrix contains the matrix we build (int[][])
//set contains the number of 1 we can use on a set (int[])
//c is the column number (int)
//r is the row number (int)
function f ( matrix, set, c, r ) :
  if ( c == N ):
    r = r + 1
    c = r

  if ( r == N ):
    write ( matrix in File )
    // Implement your own way of storing the matrix

  if ( set[r] > 0 AND (c+2 < N AND set[c+2] > 0) ):
    matrix[c][r] = 1
    set[c]--
    set[r]--
    f ( matrix, set, c+1, r )

  matrix[c][r] = 0
  f ( matrix, set, c+1, r)
end

//Calling our function with N = 5
N = 5
f([[0,0,0,0,0],[0,0,0,0,0],...], [3,2,2,2,2], 0, 0)

您可以将每个矩阵存储在文件以外的其他内容中，但请注意您的内存消耗。