是否有一种有效的算法用于有限数量的整数分区?

2022-01-17 00:00:00 algorithm math numbers java integer-partition

我必须创建一个接受两个整数的方法，让它们分别为 n 和 m，并返回有多少种方法求和 m 正数得到 n.例如，像 partition(6, 2) 这样的方法调用应该返回 3，因为有 3 种可能的方式.它们是 5 + 1、4 + 2 和 3 + 3.顺便说一句，4 + 2 与 2 + 4 相同，因此该方法不应将它们视为两个不同的变体.有人知道这个问题的解决方案吗?

I have to create a method that takes two integers, let them be n and m, and returns how many ways there are to sum m positive numbers to get n. For example, a method call like this partition(6, 2) should return 3 because there are 3 ways possible. They are 5 + 1, 4 + 2, and 3 + 3. By the way, 4 + 2 is the same as 2 + 4, so the method should not count them as two distinct variations. Does anybody know a solution to the problem?

更新:n 和 m 不大于 150.

Updated: n and m are not greater than 150.

推荐答案

递归算法

要使用 m 部分计算整数 n 的所有分区，递归算法是显而易见的选择.对于 n, m 的情况，算法在第一部分遍历每个选项 k = 1, 2, 3...，并且对于这些选项中的每一个，它都会递归n - k, m - 1 的情况.例如:

recursive algorithm

To count all partitions of an integer n with m parts, a recursive algorithm is the obvious choice. For the case n, m, the algorithm runs through every option k = 1, 2, 3... for the first part, and for each of these options it recurses with the case n - k, m - 1. For example: 

n = 16, m = 4  
first part = 1  =>  recurse with n = 15, m = 3  
first part = 2  =>  recurse with n = 14, m = 3  
first part = 3  =>  recurse with n = 13, m = 3  
etc...

经过多次递归，到达 m = 2;那么解决方案是:

After a number of recursions, the point is reached where m = 2; then the solutions are:

first part = 1  =>  second part = n - 1  
first part = 2  =>  second part = n - 2
first part = 3  =>  second part = n - 3
etc...

所以 m = 2 的解数等于第一部分的选项数.

So the number of solutions for m = 2 equals the number of options for the first part.

要仅计算唯一解并丢弃重复项，以便不同时计算 2+4 和 4+2，仅考虑部分构成非递减序列；例如:

To count only unique solutions and discard duplicates, so that 2+4 and 4+2 are not both counted, only consider solutions where the parts form a non-decreasing sequence; for example: 

n = 9, m = 3  
partitions: 1+1+7   1+2+6   1+3+5   1+4+4  
            2+2+5   2+3+4  
            3+3+3

在上升序列中，第一部分的值永远不能大于n/m.

In a rising sequence, the value of the first part can never be greater than n / m.

为了保持上升序列，每次递归都必须使用前一部分的值作为其部分的最小值；例如:

To maintain a rising sequence, every recursion must use the value of the previous part as the minimum value for its parts; for example: 

n = 9, m = 3  
k = 1  =>  recurse with n = 8, m = 2, k >= 1  =>  1+7  2+6  3+5  4+4  
k = 2  =>  recurse with n = 7, m = 2, k >= 2  =>  2+5  3+4  
k = 3  =>  recurse with n = 6, m = 2, k >= 3  =>  3+3

为了避免每次递归都传递最小值，每次递归 n - k, m - 1, k 都替换为 n - k - (m - 1) * (k - 1), m - 1, 1，解数相同.例如:

To avoid having to pass the minimum value with every recursion, every recursion n - k, m - 1, k is replaced with n - k - (m - 1) * (k - 1), m - 1, 1, which has the same number of solutions. For example:

n = 9, m = 3  
k = 1  =>  recurse with n = 8, m = 2, k >= 1  =>  1+7  2+6  3+5  4+4    
k = 2  =>  recurse with n = 5, m = 2, k >= 1  =>  1+4  2+3
k = 3  =>  recurse with n = 2, m = 2, k >= 1  =>  1+1

这不仅简化了代码，还有助于提高使用记忆的效率，因为像 2+2+3、3+3+4 和 5+5+6 全部被它们的规范形式 1+1+2 替换，并且更频繁地重复更小的一组中间计算.

Not only does this simplify the code, it also helps improve efficiency when using memoization, because sequences like 2+2+3, 3+3+4 and 5+5+6 are all replaced by their canonical form 1+1+2, and a smaller set of intermediate calculations are repeated more often.

使用递归算法进行分区时，许多计算会重复多次.并且随着 n 和 m 值的增加，递归的数量迅速变得巨大；例如解决案例 150, 23(如下图所示)，案例 4, 2 计算了 23,703,672 次.

When partitioning with a recursive algorithm, many calculations are repeated numerous times. And with increasing values for n and m, the number of recursions quickly becomes huge; e.g. to solve case 150, 23 (illustrated below), case 4, 2 is calculated 23,703,672 times.

但是，唯一计算的数量永远不能大于 n * m.因此，通过将每个计算的结果缓存在一个 n*m 大小的数组中，只需要完成 n * m 个计算；在计算了一次案例后，算法可以使用存储的值.这极大地提高了算法的效率；例如在没有记忆的情况下，需要 422,910,232 次递归来解决 150, 23 的情况；有了记忆，只需要 15,163 次递归.

However, the number of unique calculations can never be greater than n * m. So by caching the result of each calculation in an n*m-sized array, no more than n * m calculation ever need be done; after having calculated a case once, the algorithm can use the stored value. This hugely improves the algorithm's efficiency; e.g. without memoization, 422,910,232 recursions are needed to solve the case 150, 23; with memoization, only 15,163 recursions are needed.

下图显示了这种情况下的缓存读取和写入.灰色单元未使用，白色单元已写入但从不读取.总共有 2042 次写入和 12697 次读取.

The illustration below shows cache reads and writes for this case. The grey cells are unused, the white cells are written but never read. There are a total of 2042 writes and 12697 reads.

您会注意到左上角和右下角的三角形从未使用过；m的值越接近n，未使用的区域就越大.为了避免这种空间浪费，这两个三角形之间的平行四边形可以倾斜 45°，方法是将 n, m 的值存储在 n - m, m 中.缓存大小因此从 (n - 1) * (m - 1) 减少到 (n - m) * (m - 1)，最坏的情况是n,m <= 150 不再是 149 * 149 = 22201，而是 75 * 74 = 5550，不到 25% 的大小.

You'll notice that the triangles at the top left and bottom right are never used; and the closer the value of m is to n, the bigger the unused zones become. To avoid this waste of space, the parallellogram inbetween those two triangles can be skewed by 45°, by storing the value for n, m in n - m, m. The cache size is thus reduced from (n - 1) * (m - 1) to (n - m) * (m - 1), and the worst case for n,m <= 150 is no longer 149 * 149 = 22201, but 75 * 74 = 5550, less than 25% the size. 

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    if (n <= m + 1) return 1;
    var max = Math.floor(n / m);
    if (m == 2) return max;
    var count = 0;
    for (; max--; n -= m) count += partition(n - 1, m - 1);
    return count;
}

document.write(partition(6, 1) + "<br>");    // 1
document.write(partition(6, 2) + "<br>");    // 3
document.write(partition(9, 3) + "<br>");    // 7
document.write(partition(16, 4) + "<br>");   // 34
document.write(partition(150, 75) + "<br>"); // 8,118,264
// document.write(partition(150, 23));       // 1,901,740,434 (maximum for 150, takes > 10s)

此版本缓存中间结果，比基本算法快得多.即使是这个 Javascript 实现也可以在不到一毫秒的时间内解决 n=150 的最坏情况.

This version, which caches intermediate results, is much faster than the basic algorithm. Even this Javascript implementation solves the worst-case scenario for n=150 in less than a millisecond. 

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    var memo = [];
    for (var i = 0; i < n - 1; i++) memo[i] = [];
    return p(n, m);

    function p(n, m) {
        if (n <= m + 1) return 1;
        if (memo[n - 2][m - 2]) return memo[n - 2][m - 2];
        var max = Math.floor(n / m);
        if (m == 2) return max;
        var count = 0;
        for (; max--; n -= m) count += (memo[n - 3][m - 3] = p(n - 1, m - 1));
        return count;
    }
}

document.write(partition(150, 23) + "<br>");  // 1,901,740,434
// document.write(partition(1000, 81));       // 4.01779428811641e+29

(n = 1000 的最坏情况，即 m = 81，求解为 4.01779428811641e+29，这个结果也几乎立即返回.因为它超过了 Javascript 的最大安全整数 253-1，这当然不是一个确切的结果.)

(The worst case for n = 1000, which is m = 81, solves to 4.01779428811641e+29, and this result is also returned nearly instantly. Because it exceeds Javascript's maximum safe integer of 253-1, this is of course not an exact result.)

此版本使用倾斜的缓存索引来减少内存需求.

This version uses the skewed cache indexes to reduces memory requirements. 

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    var memo = [];
    for (var i = 0; i <= n - m; i++) memo[i] = [];
    return p(n, m);

    function p(n, m) {
        if (n <= m + 1) return 1;
        if (memo[n - m][m - 2]) return memo[n - m][m - 2];
        var max = Math.floor(n / m);
        if (m == 2) return max;
        var count = 0;
        for (; max--; n -= m) count += (memo[n - m][m - 3] = p(n - 1, m - 1));
        return count;
    }
}

document.write(partition(150, 23) + "<br>");  // 1,901,740,434
document.write(partition(150, 75) + "<br>");  // 8,118,264
document.write(partition(150, 127) + "<br>"); // 1255

相关文章