计算某些整数分区矩阵的算法
Algorithm to compute certain matrices of integer partitions
我寻求一种算法，该算法将枚举所有非负整数 K-by-K 矩阵，使得行和列的总和为给定值。
准确地说：给定 K 非负整数向量 m、n 和 sum(m) = sum(n)，我寻找所有矩阵 X=(x_{ij}) 这样的sum(x_{ij},i=1,...,K) = m_j 和 sum(x_{ij},j=1,...,K) = n_i。
因此每一行是n对应元素的整数分区，每一列是m.
对应元素的整数分区
这不是一个难题。给定矩阵条目的部分分配，存在一种多项式时间算法来检查是否存在至少一个令人满意的矩阵（在指定矩阵条目的任何地方具有容量 lower/upper 边界的最大流）。这直接导致多项式延迟枚举算法：遍历一棵树，其中每个内部节点对应于 "increase the current matrix entry by one" 或 "move to the next entry" 之间的决策。
你的问题可以定义为线性代数问题and/or整数线性规划。有 k x k 个变量和 k + k 个方程。可以通过标准技术（例如 Smith Normal Form）简化系统。这种方法的问题是确保所有变量都是非负的。我怀疑要找到所有的解决方案，您只需要遍历参数 space，在出现负数时停止。我怀疑是否有更有效的方法，但这只是一种直觉。
或者，您可以将该问题视为整数线性规划问题，具有常数（或其他无关紧要）objective，如 minimize 0x_{ij} 或 minimize d，其中 d不是出现在别处的变量。有关示例，请参阅 http://www.aiexp.info/calculating-all-feasible-solutions-of-ilp.html。
无论如何，回到线性代数。由于有 k^2 变量和 2k-1 约束（其中一个约束是多余的，因为所有 "across" 方程的总和等于所有 "down" 方程的总和），因此是 k^2-2k+1 = (k-1)^2 个自由变量。这应该让我们寻找自由变量的方形子矩阵。实际上，我们可以将任何方形小调（例如左上 (k-1)x(k-1) 角）视为自由。这将确定位置 (i,k)、i<k 和位置 (k,j)、j<k 中的值。最后，底角 (k,k) 由其上方或左侧的所有条目确定。 （两种方法应该一致。）
使用这个想法，我看到了两种不同的方法。第一种方法是填充以全 1 的方 (k-1)x(k-1) 子矩阵开始的自由变量，并增加它们的里程表样式。在每一步中，计算边和角变量，并在其中一个计算值达到 0 时停止增加某个数字。可以排列行和/或列，以便在战略时使用最小的总和（要么首先或者最后，我不确定）。我已经为 k=3 手动完成了这个并且它有效。就是因为有很多答案，所以花了很长时间。
更聪明的方法如下。不是确定 (k-1)x(k-1) 子矩阵，而是确定边上的其他值（(i,k) 和 (k,j) 位置）。角是 "overdetermined" 所以我们必须注意我们做事的顺序，否则就很简单了。然后告诉我们每行和每列中剩余元素的总和应该是多少，因此我们将 kxk 矩阵上的问题简化为 (k-1)x(k-1) 矩阵上的问题。也就是说，我们可以使用递归。
完成k=3问题的过程很有启发性，其中所有行和列的总和为 4。填充右边缘和下边缘的各种方法如下：
XX1 XX1 XX1 XX2 XX2
XX1 XX2 XX2 XX1 XX1
112 121 211 121 211
在第一种情况下，我们得到了简化的问题
XX = 3
XX = 3
==
33
为了解决这个问题，我们按照上面的方法进行，使用较小的矩阵。可能的边是
X1 X2
12 21
直接导致解决方案
21 12
12 21
将它们代入它们所来自的 3x3 矩阵，我们得到原始问题的以下解决方案：
211 121
121 211
112 112
接下来考虑3x3情况
XX1
XX2
121
这引起了 2x2 问题
XX=3
XX=2
==
32
在这种情况下唯一有效的边是
X1
11
给出唯一的解
21
11
代入原来的3x3情况，我们得到了原始问题的另一个解决方案，
211
112
121
等等。
我从评论中看到您正在寻找您的问题的名称，以便找到实现或一些文献。所以，你的问题名称是："Enumerating contingency tables with fixed margins" 并且实际上非常复杂（除了 2 行和 2 列的情况）。众所周知，它是#P-complete，即使您只有 2 行和 n 列。因此，通常使用近似算法来计算解决方案（或使用 mcmc 算法随机生成它们）。
奇怪的是，D.Knuth 和 F.Ruskey 都将这个问题作为练习留在了各自的书中。
This paper 提供了对精确算法和近似算法的良好（不是最新的）评论。
一个典型的应用程序是计算 Fisher 精确检验的统计数据，因此搜索它也会得到很好的结果。
我寻求一种算法，该算法将枚举所有非负整数 K-by-K 矩阵，使得行和列的总和为给定值。
准确地说：给定 K 非负整数向量 m、n 和 sum(m) = sum(n)，我寻找所有矩阵 X=(x_{ij}) 这样的sum(x_{ij},i=1,...,K) = m_j 和 sum(x_{ij},j=1,...,K) = n_i。
因此每一行是n对应元素的整数分区，每一列是m.
这不是一个难题。给定矩阵条目的部分分配，存在一种多项式时间算法来检查是否存在至少一个令人满意的矩阵（在指定矩阵条目的任何地方具有容量 lower/upper 边界的最大流）。这直接导致多项式延迟枚举算法：遍历一棵树，其中每个内部节点对应于 "increase the current matrix entry by one" 或 "move to the next entry" 之间的决策。
你的问题可以定义为线性代数问题and/or整数线性规划。有 k x k 个变量和 k + k 个方程。可以通过标准技术（例如 Smith Normal Form）简化系统。这种方法的问题是确保所有变量都是非负的。我怀疑要找到所有的解决方案，您只需要遍历参数 space，在出现负数时停止。我怀疑是否有更有效的方法，但这只是一种直觉。
或者，您可以将该问题视为整数线性规划问题，具有常数（或其他无关紧要）objective，如 minimize 0x_{ij} 或 minimize d，其中 d不是出现在别处的变量。有关示例，请参阅 http://www.aiexp.info/calculating-all-feasible-solutions-of-ilp.html。
无论如何，回到线性代数。由于有 k^2 变量和 2k-1 约束（其中一个约束是多余的，因为所有 "across" 方程的总和等于所有 "down" 方程的总和），因此是 k^2-2k+1 = (k-1)^2 个自由变量。这应该让我们寻找自由变量的方形子矩阵。实际上，我们可以将任何方形小调（例如左上 (k-1)x(k-1) 角）视为自由。这将确定位置 (i,k)、i<k 和位置 (k,j)、j<k 中的值。最后，底角 (k,k) 由其上方或左侧的所有条目确定。 （两种方法应该一致。）
使用这个想法，我看到了两种不同的方法。第一种方法是填充以全 1 的方 (k-1)x(k-1) 子矩阵开始的自由变量，并增加它们的里程表样式。在每一步中，计算边和角变量，并在其中一个计算值达到 0 时停止增加某个数字。可以排列行和/或列，以便在战略时使用最小的总和（要么首先或者最后，我不确定）。我已经为 k=3 手动完成了这个并且它有效。就是因为有很多答案，所以花了很长时间。
更聪明的方法如下。不是确定 (k-1)x(k-1) 子矩阵，而是确定边上的其他值（(i,k) 和 (k,j) 位置）。角是 "overdetermined" 所以我们必须注意我们做事的顺序，否则就很简单了。然后告诉我们每行和每列中剩余元素的总和应该是多少，因此我们将 kxk 矩阵上的问题简化为 (k-1)x(k-1) 矩阵上的问题。也就是说，我们可以使用递归。
完成k=3问题的过程很有启发性，其中所有行和列的总和为 4。填充右边缘和下边缘的各种方法如下：
XX1 XX1 XX1 XX2 XX2
XX1 XX2 XX2 XX1 XX1
112 121 211 121 211
在第一种情况下，我们得到了简化的问题
XX = 3
XX = 3
==
33
为了解决这个问题，我们按照上面的方法进行，使用较小的矩阵。可能的边是
X1 X2
12 21
直接导致解决方案
21 12
12 21
将它们代入它们所来自的 3x3 矩阵，我们得到原始问题的以下解决方案：
211 121
121 211
112 112
接下来考虑3x3情况
XX1
XX2
121
这引起了 2x2 问题
XX=3
XX=2
==
32
在这种情况下唯一有效的边是
X1
11
给出唯一的解
21
11
代入原来的3x3情况，我们得到了原始问题的另一个解决方案，
211
112
121
等等。
我从评论中看到您正在寻找您的问题的名称，以便找到实现或一些文献。所以，你的问题名称是："Enumerating contingency tables with fixed margins" 并且实际上非常复杂（除了 2 行和 2 列的情况）。众所周知，它是#P-complete，即使您只有 2 行和 n 列。因此，通常使用近似算法来计算解决方案（或使用 mcmc 算法随机生成它们）。
奇怪的是，D.Knuth 和 F.Ruskey 都将这个问题作为练习留在了各自的书中。
This paper 提供了对精确算法和近似算法的良好（不是最新的）评论。
一个典型的应用程序是计算 Fisher 精确检验的统计数据，因此搜索它也会得到很好的结果。