我试图找到一个算法(不是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
然后应该可以找到矩阵值的每个可能组合:
-
在每个可能的4个单元组的第一个矩阵上应用算法;
-
对于除了在父执行中已经使用的任何组之外的每个可能的4个单元组,递归地将算法应用于由前一次迭代获得的每个子矩阵;
递归深度应为 (N*(N-1)/2)*(M*(M-1)/2)
,每次执行都会产生 ((N*(N-1)/2)*(M*(M-1)/2) - depth)*(I+J+1)
子矩阵 . 但是这会产生很多重复的矩阵,所以这可能会被优化 .
2 回答
你需要这个来计算Fisher's exact test吗?因为如果你想要每个解决方案,那么你需要做的事情比强力递归枚举更好 . OTOH似乎蒙特卡洛近似成功地被某些软件使用而不是完整的枚举 .
我问了一个similar question,这可能会有所帮助 . 虽然这个问题涉及保留每行和每列中字母的频率而不是总和,但一些结果可以翻译出来 . 例如 . 如果你找到任何子矩阵(一对不一定相邻的行和一对不一定相邻的列)与数字
然后你可以重新安排这些
不改变任何行或列的总和 . 然而:
mhum's answer证明通常存在任何此类2x2交换序列无法达到的有效矩阵 . 这可以通过获取他的3x3矩阵并映射
A -> 1
,B -> 2
,C -> 4
并注意到,因为没有元素在行或列中出现多次,原始矩阵中的频率保留相当于新矩阵中的保存 . 然而...someone's answer链接到一个数学证明,它实际上适用于条目为0或1的矩阵 .
更一般地说,如果你有任何子矩阵
其中(不一定是唯一的)最小值是d,那么你可以用任何d 1矩阵替换它
其中h = d-i,g = c i,f = b i且e = a-i,对于任何整数0 <= i <= d .
对于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