用条件查找所有可能的二进制组合的算法

Question

这是一个适合你的数学大脑.我有一个矩阵,实际上是它的一半矩阵,对角切割.矩阵的每个元素可以是1或0.我需要为宽度为N的任何矩阵找到1 s和0 s的所有可能组合.

这很容易,您可以在给定宽度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

这是入门的基本想法；虽然它太大了，无法发表评论，但不是完整的答案。

这个想法是从一个最大程度“填充”的矩阵开始，而不是一个空的矩阵，然后填充它。

基本剥离程序

从一个矩阵开始，所有行都填充到最大数量的1s，即第 0 行有 4 1s，其他行每行有 3 1s。然后，开始检查条件。条件 0（第 0 行）自动满足。对于其余的条件，要么满足，要么其条件集中的s太多1：去掉1s，直到条件满足。对所有条件都执行此操作。

生成所有“更简单”的

这样做，您最终会得到一个满足所有条件的矩阵。现在，您可以将 any 更改1为 a 0，矩阵仍然满足所有条件。因此，一旦有了“最大”解决方案，您就可以轻松生成它的所有子解决方案。