是否有一种有效的算法用于具有有限数量的部分的整数分区? [英] Is there an efficient algorithm for integer partitioning with restricted number of parts?

问题描述

我必须创建一个接受两个整数的方法，让它们是 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 值的增加，递归的数量很快变得巨大；例如为了解决case 150, 23(如下图所示)，case 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，未使用的区域就越大.为了避免这种空间浪费，通过将 n, m 的值存储在 n - m, m 中，可以将这两个三角形之间的平行四边形倾斜 45°.缓存大小因此从 (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 的最大安全整数 2⁵³-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 2⁵³-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

这篇关于是否有一种有效的算法用于具有有限数量的部分的整数分区?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！