枚举具有固定行和列和的矩阵组合

Question

我试图找到一种算法（不是matlab命令）来枚举所有可能的NxM矩阵，其约束条件是每个单元格中只有正整数（或0）以及每行和每列的固定和（这些是算法的参数）。

例：枚举所有2x3矩阵，行总计为2,1，列总计为0,1,2：

| 0 0 2 | = 2
| 0 1 0 | = 1
  0 1 2

| 0 1 1 | = 2
| 0 0 1 | = 1
  0 1 2

这是一个相当简单的例子，但是随着N和M的增加，以及总和的增加，可能会有很多可能性。

编辑1

我可能有一个有效的安排来启动算法：

matrix = new Matrix(N, M) // NxM matrix filled with 0s
FOR i FROM 0 TO matrix.rows().count()
  FOR j FROM 0 TO matrix.columns().count()
    a = target_row_sum[i] - matrix.rows[i].sum()
    b = target_column_sum[j] - matrix.columns[j].sum()
    matrix[i, j] = min(a, b)
  END FOR
END FOR

target_row_sum[i]是第一行的预期金额。

在上面的例子中，它给出了第二种安排。

编辑2：（根据j_random_hacker最后的陈述）

设M为验证给定条件的任意矩阵（行和列和固定、正或空单元格值）。设（a，b，c，d）为M中的4个单元格值，其中（a，b）和（c，d）在同一行上，（a，c）和（b，d）在同一列上。设Xa为包含a的单元格的行号，Ya为其列号。

示例：

| 1 a b |
| 1 2 3 |
| 1 c d |
-> Xa = 0, Ya = 1
-> Xb = 0, Yb = 2
-> Xc = 2, Yc = 1
-> Xd = 2, Yd = 2

这里有一个算法，可以得到所有的组合，验证初始条件，只使a，b，c和d变化：

// A matrix array containing a single element, M
// It will be filled with all possible combinations
matrices = [M]

I = min(a, d)
J = min(b, c)
FOR i FROM 1 TO I
    tmp_matrix = M
    tmp_matrix[Xa, Ya] = a - i
    tmp_matrix[Xb, Yb] = b + i
    tmp_matrix[Xc, Yc] = c - i
    tmp_matrix[Xd, Yd] = d + i
    matrices.add(tmp_matrix)
END FOR
FOR j FROM 1 TO J
    tmp_matrix = M
    tmp_matrix[Xa, Ya] = a + j
    tmp_matrix[Xb, Yb] = b - j
    tmp_matrix[Xc, Yc] = c + j
    tmp_matrix[Xd, Yd] = d - j
    matrices.add(tmp_matrix)
END FOR

然后应能找到矩阵值的所有可能组合：

1. 对每个可能的4个单元组的第一个矩阵应用该算法
2. 递归地将算法应用于通过上一次迭代获得的每个子矩阵，用于除已在父执行中使用的任何组之外的每个可能的4个单元组

递归深度应为（N*（N-1）/2）*（M*（M-1）/2），每次执行产生（（N*（N-1）/2）*（M*（M-1）/2）-深度）*（I J 1）子矩阵。但这会产生大量重复矩阵，因此可能会对其进行优化。

Answer 1

对于NXM矩阵，有NXM未知数和nm方程。将随机数放在左上角（N-1）X（M-1）子矩阵上，除了（N-1，M-1）元素。现在，您可以轻松地找到其余N M元素的闭合形式。

更多细节：共有T=N*M个元素

有R=（N-1）（M-1）-1个随机填写的元素。

剩余未知数：T-S=N*M-（N-1）*（M-1）1=N*M

Answer 2

你需要这个来计算费希尔的精确测试吗？因为这需要您正在做的事情，并且基于该页面，似乎通常会有大量的解决方案，所以如果您想要每个解决方案，您可能不会比暴力递归枚举做得更好。OTOH似乎蒙特卡罗近似被一些软件成功地使用，而不是成熟的枚举。

我问了一个类似的问题，这可能会有所帮助。虽然这个问题涉及的是保持每行和每列中字母的频率，而不是求和，但有些结果可以跨行翻译。例如，如果您找到任何带有数字的子矩阵（一对不一定相邻的行和一对不一定相邻的列）

xy
yx

然后你可以把这些重新排列成

yx
xy

不更改任何行或列和。然而：

• mhum的回答证明，通常存在有效矩阵，这些矩阵不能通过任何2x2交换序列来达到。这可以通过他的3x3矩阵和映射A来看出-

更一般地说，如果你有任何子矩阵

ab
cd

如果（不一定是唯一的）最小值是d，那么可以用任何d1矩阵替换它

ef
gh

其中h=d-i，g=c i，f=b i和e=a-i，对于任意整数0