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

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]是在第i行预期的总和。

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

---

编辑2： （基于j_random_hacker's last statement）

设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) - depth)*(I+J+1)子矩阵。但是这会产生很多重复的矩阵，所以这可能会被优化。

Answer 1

对于NXM矩阵，您有NXM未知数和N + M个方程。将随机数放到左上（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

你需要这个计算Fisher's exact test？因为这需要你在做什么，并且基于那个页面，看起来通常会有大量的解决方案，所以如果你想要每个解决方案的话，你可能无法比暴力递归枚举更好。 OTOH似乎蒙特卡罗近似值被一些软件成功使用，而不是全面的枚举。

我问了一个similar question，这可能会有所帮助。虽然这个问题涉及保留每行和每列字母的频率而不是和，但是可以将一些结果翻译出来。例如。如果您发现有数字的任何子矩阵（对未不一定相邻行对未不一定相邻列的）

xy 
yx 

然后，你可以重新排列这些到

yx 
xy 

无需更改任何一行或列总和。但是：

• mhum's answer证明通常将有有效的矩阵不能通过任何这样的2x2交换序列达到。这可以通过拍摄他的3x3矩阵和映射A -> 1,B -> 2,C -> 4来看出，并且注意到，因为没有元素在一行或一列中出现超过一次，所以原始矩阵中的频率保持等同于新矩阵中的和保存。 但是...
• someone's answer链接到一个数学证明，它实际上会为基质，其条目是刚刚0或1

更一般地，如果您有任何小矩阵工作

ab 
cd 

其中（不必是唯一的）最小值为d，那么您可以用任何d + 1矩阵代替它

ef 
gh 

其中h = d-i，g = c + i，f = b + i且e = a-i，对于任何整数0 < = i < = d。