首页 文章

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

提问于
浏览
2

我试图找到一个算法(不是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 回答

  • 1

    你需要这个来计算Fisher's exact test吗?因为如果你想要每个解决方案,那么你需要做的事情比强力递归枚举更好 . OTOH似乎蒙特卡洛近似成功地被某些软件使用而不是完整的枚举 .

    我问了一个similar question,这可能会有所帮助 . 虽然这个问题涉及保留每行和每列中字母的频率而不是总和,但一些结果可以翻译出来 . 例如 . 如果你找到任何子矩阵(一对不一定相邻的行和一对不一定相邻的列)与数字

    xy
    yx
    

    然后你可以重新安排这些

    yx
    xy
    

    不改变任何行或列的总和 . 然而:

    • mhum's answer证明通常存在任何此类2x2交换序列无法达到的有效矩阵 . 这可以通过获取他的3x3矩阵并映射 A -> 1B -> 2C -> 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 .

  • 0

    对于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

相关问题