2

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

示例：枚举所有行总数为 2、1 和列总数为 0、1、2 的 2x3 矩阵：

| 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 的最后一条语句）

让 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)子矩阵。但这会产生很多重复的矩阵，所以这可能会被优化。

4

2 回答 2

1

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

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

xy
yx

然后你可以重新排列这些

yx
xy

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

  • mhum 的回答证明，通常会有任何此类 2x2 交换序列无法达到的有效矩阵。这可以通过他的 3x3 矩阵和映射A -> 1,来看出B -> 2，C -> 4并注意到，因为没有元素在一行或一列中出现多次，所以原始矩阵中的频率保留等同于新矩阵中的和保留。 然而...
  • 某人的答案链接到数学证明，它实际上适用于条目仅为 0 或 1 的矩阵。

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

ab
cd

其中（不一定唯一）最小值是 d，那么您可以将其替换为任何 d+1 矩阵

ef
gh

其中 h = di，g = c+i，f = b+i 和 e = ai，对于任何整数 0 <= i <= d。

于 2013-07-26T15:31:14.047 回答
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 个随机填充的元素。

剩余未知数：TS = N*M - (N-1)*(M-1) +1 = N+M

于 2013-07-25T15:50:20.047 回答