是否有一个有效的整数分区算法,有限的零件数量？

Question

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

更新:n和m不大于150.

Answer 1

递归算法

要计算n具有m部分的整数的所有分区,递归算法是显而易见的选择.对于这种情况n, m,算法会遍历k = 1, 2, 3...第一部分的每个选项,并且对于每个选项,它都会根据案例进行处理n - k, m - 1.例如:

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; 然后解决方案是:

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

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

上升序列

要仅计算唯一解决方案并丢弃重复项,以便同时计算2+4和4+2不计算,只考虑其中部分形成非递减序列的解决方案; 例如:

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.

最小值为1的递归

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

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具有相同数量的解决方案.例如:

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

这不仅简化了代码,还有助于提高使用memoization时的效率,因为序列喜欢2+2+3,3+3+4并且5+5+6都被其规范形式所取代1+1+2,并且更少的中间计算更频繁地重复.

记忆化

当使用递归算法进行分区时,许多计算会重复多次.随着n和m值的增加,递归的次数很快变得很大; 例如,为了解决案例150, 23(如下图所示),案例4, 2计算为23,703,672次.

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

下图显示了此案例的缓存读取和写入.灰色单元格未使用,白色单元格已写入但从未读取过.总共有2042次写入和12697次读取.

减少缓存大小

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

代码示例1:没有memoization

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)

代码示例2:具有memoization的快速版本

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

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,这当然不是确切的结果.)

代码示例3:具有memoization和较小缓存的快速版本

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

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