一种计算整数网格数的有效算法

Question

考虑一个正方形3乘3的非负整数网格。对于每行i，整数之和设置为r_i。类似地，对于每列j，该列中的整数之和设置为c_j。因此，6非负整数描述了问题的一个例子。

是否存在一种有效的算法来计算在给定行和列和约束的情况下有多少不同的整数赋值给网格？

很明显，人们可以枚举所有可能的非负整数矩阵，其值最大为sum r_i，并检查每个矩阵的约束，但这将非常慢。

例

假设行约束是1 2 3，列约束是3 2 1。可能的整数网格是：

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 1│0 0 1│0 0 1│0 1 0│0 1 0│0 1 0│0 1 0│1 0 0│1 0 0│1 0 0│1 0 0│1 0 0│
│0 2 0│1 1 0│2 0 0│0 1 1│1 0 1│1 1 0│2 0 0│0 1 1│0 2 0│1 0 1│1 1 0│2 0 0│
│3 0 0│2 1 0│1 2 0│3 0 0│2 1 0│2 0 1│1 1 1│2 1 0│2 0 1│1 2 0│1 1 1│0 2 1│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

在实践中，我的主要兴趣是当网格的总和最多为100时，但更通用的解决方案将非常有趣。

Answer 1

这对＃P-hard问题没有帮助（如果允许矩阵具有任何大小 - 请参阅下面的注释中的参考），但有一个解决方案不等于列举所有矩阵而是一组较小的物体叫做semi-standard Young tableaux。根据您的输入，它可能会更快，但仍然具有指数复杂性。由于它是几本代数组合学书或Knuth的AOCP 3中的完整章节，因此我不会在此处详细说明相关的维基百科页面。

这个想法是使用Robinson–Schensted–Knuth correspondence这些矩阵中的每一个都使用一对相同形状的表格进行双射，其中一个画面用行总和计算整数，另一个用列总和填充。用V计数的数字填充的形状U的表格数被称为Kostka Number K（U，V）。结果，你最终得到了一个公式，如

#Mat(RowSum, ColSum) = \sum_shape  K(shape, RowSum)*K(shape, ColSum)

当然如果RowSum == ColSum == Sum：

#Mat(Sum, Sum) = \sum_shape  K(shape, Sum)^2

以下是SageMath系统中的示例：

sage: sum(SemistandardTableaux(p, [3,2,1]).cardinality()^2 for p in  Partitions(6))
12

以下是一些更大的例子：

sage: sums = [6,5,4,3,2,1]
sage: %time sum(SemistandardTableaux(p, sums).cardinality()^2 for p in Partitions(sum(sums)))
CPU times: user 228 ms, sys: 4.77 ms, total: 233 ms
Wall time: 224 ms
8264346

sage: sums = [7,6,5,4,3,2,1]
sage: %time sum(SemistandardTableaux(p, sums).cardinality()^2 for p in Partitions(sum(sums)))
CPU times: user 1.95 s, sys: 205 µs, total: 1.95 s
Wall time: 1.94 s
13150070522

sage: sums = [5,4,4,4,4,3,2,1]
sage: %time sum(SemistandardTableaux(p, sums).cardinality()^2 for p in Partitions(sum(sums)))
CPU times: user 1.62 s, sys: 221 µs, total: 1.62 s
Wall time: 1.61 s
1769107201498

很明显，你不会得到那么快的枚举矩阵。

根据גלעדברקן@的要求，这是一个具有不同行和列总和的解决方案：

sage: rsums = [5,4,3,2,1]; colsums = [5,4,3,3]
sage: %time sum(SemistandardTableaux(p, rsums).cardinality() * SemistandardTableaux(p, colsums).cardinality() for p in Partitions(sum(rsums)))
CPU times: user 88.3 ms, sys: 8.04 ms, total: 96.3 ms
Wall time: 92.4 ms
10233

Answer 2

是否存在一种有效的算法来计算在给定行和列和约束的情况下有多少不同的整数赋值给网格？

upd当N固定时（即变为常数3），我的答案对于这个特殊问题是错误的。在这种情况下，它是多项式。很抱歉有误导性的信息。

TL; DR：我认为这至少是NP难的。没有polinomial算法，但也许有一些启发式加速。

对于N-by-N网格，您有行和的N方程，col和N方程和N^2非负约束：

对于N > 2，该系统通常具有多种可能的解决方案。因为有N^2未知变量x_ij和2N等式=>对于N > 2：N^2 > 2N。

你可以消除2N - 1变量只留下一个方程式，K = N^2 - (2N-1)变量得到总和S。那么你将不得不与integer partition problem打交道，找出所有可能的K术语组合来获得S。这个问题是NP完全的。并且组合的数量不仅取决于术语K的数量，还取决于值S的顺序。

这个问题让我想起了Simplex method。我的第一个想法是使用类似方法找到一个解决方案，然后遍历凸边以找到所有可能的解决方案。我希望有一个最佳算法。但不，整数单纯形法，与integer linear programming有关，是NP难:(

我希望，对于可以用来加速天真蛮力解决方案的相关问题，有一些启发式方法。

Answer 3

我不知道匹配的算法，但我认为没有一个难以解决。给定任何一种解决方案，您可以通过选择网格矩形区域的四个角来获得另一种解决方案，将两个对角线增加一些值，并将另外两个角减少相同的值。该值的范围将受每个对角线对的最低值约束。如果确定所有此类范围的大小，则应该能够将它们相乘以确定可能的总解决方案。

假设您将网格描述为按字母顺序排列的熟悉的电子表格，以及数字表示行，您可以在以下列表中描述所有可能的区域：

A1:B2, A1:B3, A1:C2, A1:C3, B1:C2, B1:C3, A2:B3, A2:C3, B2:C3

对于每个区域，我们根据每个对角线对的最低值制表一个范围。您可以递增地减少任一对，直到成员达到零，因为另一对没有上限。

选择示例的第一个解决方案，我们可以使用此技术推导出所有其他可能的解决方案。

   A B C
  ┌─────┐
1 │0 0 1│ sum=1
2 │0 2 0│ sum=2
3 │3 0 0│ sum=3
  └─────┘
   3 2 1 = sums

A1:B2 - 1 solution (0,0,0,2)
A1:C2 - 1 solution (0,1,0,0)
A1:B3   1 solution (0,0,3,0)
A1:C3   2 solutions (0,1,3,0), (1,0,2,1)
B1:C2   2 solutions (0,1,2,0), (1,0,1,1)
B1:C3   1 solution (0,1,0,0)
A2:B3   3 solutions (0,2,3,0), (1,1,2,1), (2,0,1,2)
A2:C3   1 solution (0,0,3,0)
B2:C3   1 solution (2,0,0,0)

将所有解决方案计数相乘，即可获得2 * 2 * 3 = 12个解决方案。

Answer 4

如果总和很小，也许一个简单的4嵌套循环解决方案足够快？

function solve(rowsum, colsum) {
    var count = 0;
    for (var a = 0; a <= rowsum[0] && a <= colsum[0]; a++) {
        for (var b = 0; b <= rowsum[0] - a && b <= colsum[1]; b++) {
            var c = rowsum[0] - a - b;
            for (var d = 0; d <= rowsum[1] && d <= colsum[0] - a; d++) {
                var g = colsum[0] - a - d;
                for (var e = 0; e <= rowsum[1] - d && e <= colsum[1] - b; e++) {
                    var f = rowsum[1] - d - e;
                    var h = colsum[1] - b - e;
                    var i = rowsum[2] - g - h;
                    if (i >= 0 && i == colsum[2] - c - f) ++count;
                }
            }
        }
    }
    return count;
}
document.write(solve([1,2,3],[3,2,1]) + "<br>");
document.write(solve([22,33,44],[30,40,29]) + "<br>");

Answer 5

我已经厌倦了优化慢速选项。我得到所有组合并仅更改代码以获得总计数。这是我能得到的最快的：

    private static int count(int[] rowSums, int[] colSums)
    {
        int count = 0;
        int[] row0 = new int[3];
        int sum = rowSums[0];
        for (int r0 = 0; r0 <= sum; r0++)
            for (int r1 = 0, max1 = sum - r0; r1 <= max1; r1++)
            {
                row0[0] = r0;
                row0[1] = r1;
                row0[2] = sum - r0 - r1;
                count += getCombinations(rowSums[1], row0, colSums);
            }                    
        return count;
    }
    private static int getCombinations(int sum, int[] row0, int[] colSums)
    {
        int count = 0;
        int max1 = Math.Min(colSums[1] - row0[1], sum);
        int max2 = Math.Min(colSums[2] - row0[2], sum);
        for (int r0 = 0, max0 = Math.Min(colSums[0] - row0[0], sum); r0 <= max0; r0++)
            for (int r1 = 0; r1 <= max1; r1++)
            {
                int r01 = r0 + r1;
                if (r01 <= sum)
                    if ((r01 + max2) >= sum)
                        count++;
            }
        return count;
    }




Stopwatch w2 = Stopwatch.StartNew();
int res = count(new int[] { 1, 2, 3 }, new int[] { 3, 2, 1 });//12
int res1 = count(new int[] { 22, 33, 44 }, new int[] { 30, 40, 29 });//117276
int res2 = count(new int[] { 98, 99, 100}, new int[] { 100, 99, 98});//12743775
int res3 = count(new int[] { 198, 199, 200 }, new int[] { 200, 199, 198 });//201975050
w2.Stop();
Console.WriteLine("w2:" + w2.ElapsedMilliseconds);//322 - 370 on my computer

Answer 6

除了我使用Robinson-Schensted-Knuth双射的另一个答案，这里是另一个不需要高级组合的解决方案，但编程中的一些技巧解决了任意较大矩阵的这个问题。应该用来解决这类问题的第一个想法是使用递归，避免重新计算，这要归功于一些记忆或更好的动态编程。特别是一旦你为第一行选择了一个候选者，你将第一行减去列总和，只剩下少一行，你就会遇到同样的问题。为避免重新计算事物，请存储结果。你可以这样做

要么基本上在一张大桌子（memoization）
或者以更棘手的方式存储具有n行的矩阵的所有解，并推导出具有n + 1行的矩阵的解的数量（动态编程）。

这是一个在Python中使用memoization的递归方法：

 # Generator for the rows of sum s which are smaller that maxrow
 def choose_one_row(s, maxrow):
     if not maxrow:
         if s == 0: yield []
         else: return
     else:
         for i in range(0, maxrow[0]+1):
             for res in choose_one_row(s-i, maxrow[1:]):
                 yield [i]+res


 memo = dict()
 def nmat(rsum, colsum):
     # sanity check: sum by row and column must match
     if sum(rsum) != sum(colsum): return 0
     # base case rsum is empty
     if not rsum: return 1
     # convert to immutable tuple for memoization
     rsum = tuple(rsum)
     colsum = tuple(colsum)
     # try if allready computed
     try:
         return memo[rsum, colsum]
     except KeyError:
         pass
     # apply the recursive formula
     res = 0
     for row in choose_one_row(rsum[0], colsum):
         res += nmat(rsum[1:], tuple(a - b for a, b in zip(colsum, row)))
     # memoize the result
     memo[(tuple(rsum), tuple(colsum))] = res
     return res

之后：

sage: nmat([3,2,1], [3,2,1])
12

sage: %time nmat([6,5,4,3,2,1], [6,5,4,3,2,1])
CPU times: user 1.49 s, sys: 7.16 ms, total: 1.5 s
Wall time: 1.48 s
8264346

一种计算整数网格数的有效算法

问题描述投票：15回答：6

6个回答

最新问题

一种计算整数网格数的有效算法

问题描述 投票：15回答：6

6个回答

最新问题

问题描述投票：15回答：6