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

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

这很容易，您可以在给定宽度 N 的情况下获得此矩阵上的元素数，对于此示例， N = 7 这将为我们提供 28 或元素数。然后，您可以使用来获得组合。

因此，公式将是获取所有可能的组合。



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



这是此示例的集合( N = 7 )的样子。如果您注意到每行都有代表。因此，对于第一个集合，如果组合为 0 1 0 1 0 1 0 ，则其总和 1 0 0 0 0 1 0 ，则有效，因为它必须小于3。









我需要对庞大的矩阵执行此操作，因此强行强制所有可能的排列以找到属于此条件的排列是不可行的。我需要找到一种算法，可以用来自底向上而不是自顶向下生成有效矩阵。也许做一些单独的操作，这些操作可以在以后组合起来以产生总的结果。

任何想法都欢迎。

最佳答案

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

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)

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

关于c# - 查找具有条件的所有可能二进制组合的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32599254/