2

我一直在寻找一种算法来解决所有可能的维度为“n”的矩阵，这些矩阵可以通过两个数组获得，一个是行的总和，另一个是矩阵的列的总和。例如，如果我有以下维数为 7 的矩阵：

matriz= [ 1  0  0  1  1  1  0
          1  0  1  0  1  0  0
          0  0  1  0  1  0  0
          1  0  0  1  1  0  1
          0  1  1  0  1  0  1
          1  1  1  0  0  0  1
          0  0  1  0  1  0  1 ]

列的总和是：

col= [4 2 5 2 6 1 4]

行的总和是：

行 = [4 3 2 4 4 4 3]

现在，我想获得所有可能的“一和零”矩阵，其中列和行的总和分别满足“col”和“row”的条件。

我会很感激可以帮助解决这个问题的想法。

4

1 回答 1

1

一个明显的方法是暴力破解解决方案：对于第一行，生成所有具有正确总和的可能性，然后对于其中的每一个，生成第二行的所有可能性，依此类推。生成所有行后，检查列的总和是否正确。但这需要很多时间。我的数学在一天中的这个时候可能会生疏，但我相信长度n为k1 的行的不同可能性的数量由二项式系数或nchoosek(n,k)在 Matlab 中给出。要确定可能性的总数，您必须将此数字乘以每一行：

>> n = 7;
>> row= [4 3 2 4 4 4 3];
>> prod(arrayfun(@(k) nchoosek(n, k), row))
ans =
   3.8604e+10

这是很多检查的可能性！对列执行相同操作会给出

>> col= [4 2 5 2 6 1 4];
>> prod(arrayfun(@(k) nchoosek(n, k), col))
ans =
   555891525

仍然是一个很大的数字，但“仅”小了 70 倍。

通过查看后面的行是否已经受到前面的行的约束，可以稍微改进这种蛮力方法。如果在您的示例中，对于前两行的特定组合，两行在第二列中都有 1，则该列的其余部分都应为 0，因为总和必须为 2。这减少了剩下的行有点。实施此类检查可能会使事情变得有些复杂，但它们可能会在需要 2 天的计算或仅需要 1 小时的计算之间产生差异。

对此的优化版本可能会交替生成行和列，并从可能性数量最少的那些开始。我不知道是否有比这种蛮力方法更优雅的解决方案，我很想听听。

于 2013-10-13T22:12:45.843 回答