15

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

更新：n并且m不大于 150。

4

6 回答 6

13

递归算法

n用部分计算整数的所有分区m，递归算法是显而易见的选择。对于 case n, m，算法遍历k = 1, 2, 3...第一部分的每个选项，并且对于这些选项中的每一个，它都会与 case 一起递归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

这不仅简化了代码，还有助于提高使用记忆的效率，因为像和之类的序列都被它们的规范形式所取代2+2+3，并且更频繁地重复了较小的一组中间计算。 3+3+45+5+61+1+2

记忆

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

n,m = 150,23 的递归热图

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

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

n,m = 150,23 的缓存热图

减少缓存大小

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

n,m = 150,23 的倾斜缓存热图

代码示例 1：没有记忆

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：带记忆的快速版本

此版本缓存中间结果，比基本算法快得多。即使这个 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 53 -1，这当然不是准确的结果。）

代码示例 3：具有记忆和较小缓存的快速版本

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

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

于 2015-10-03T02:52:48.510 回答
4

您可以使用动态编程。设为非递减正数f[n][m][k]的分区数，使得总和为，最后一个为。然后你可以很容易地看到更新步骤是：mnk

f[n][m][k] → f[n+l][m+1][l] for every l≥ k

要得到f[n][m]，意味着独立于最后一个数字的所有分区的数量，最后只需对所有 求和k。复杂性是O(n^2 m).

于 2015-10-02T13:02:09.227 回答
2 
public static long p(final long n, final long m) {
    System.out.println("n=" + n + ", m=" + m);
    return p(n, 1, m);
}

private static long p(final long n, final long digitFrom, final long m) {
    final long digitTo = n - m + 1;
    if (digitFrom > digitTo) return 0;
    if (m == 1) return 1;
    long sum = 0;
    for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++)
        sum += p(n - firstDigit, firstDigit, m - 1);
    return sum;
}

示例调试：

n=6, m=3
1+1+4
1+2+3
2+2+2

从调试版本：

public static long p(final long n, final long m) {
    System.out.println("n=" + n + ", m=" + m);
    return p(n, 1, m, new Stack<String>());
}

private static long p(final long n, final long digitFrom, final long m, Stack<String> digitStack) {
    final long digitTo = n - m + 1;
    if (digitFrom > digitTo) return 0;
    if (m == 1) {
        digitStack.push(n + "");
        printStack(digitStack);
        digitStack.pop();
        System.out.println();
        return 1;
    }
    long sum = 0;
    for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++) {
        digitStack.push(firstDigit + "+");
        sum += p(n - firstDigit, firstDigit, m - 1, digitStack);
        digitStack.pop();
    }
    return sum;
}
于 2015-10-02T12:57:53.820 回答
0

映射和减少方法

你可以先准备加数序列，然后成对依次处理，逐步得到笛卡尔积。

作为一个和数序列，您可以使用TreeMap<int[]>比较器来比较两个排序数组的内容，以消除重复组合，例如4+2和2+4。如果要保留这些组合，可以使用 2D 数组int[][]代替。这稍微简化了代码，但需要更多的计算时间。

如果n = 6，则加法序列如下：

1: [1][2][3][4][5][6]
2: [1][2][3][4][5]
3: [1][2][3][4]
4: [1][2][3]
5: [1][2]
6: [1]

该reduce方法经过5阶段，依次获得笛卡尔积：

1: [1][2][3][4][5][6]
2: [1][2][3][4][5]
---
sum1: [1,1][1,2][1,3]...[2,1][2,2][2,3]...
3: [1][2][3][4]
---
sum2: [1,1,1][1,2,1]...[2,1,1][2,2,1]...[3,1,1][3,2,1]...
4: [1][2][3]
---
sum3: [1,1,1,1]...[2,1,1,1]...[3,1,1,1]...
5: [1][2]
---
sum4: [1,1,1,1,1]...[2,1,1,1,1]...
6: [1]
---
total: [1,1,1,1,1,1]...

在减少的每一步中，那些大于指定数量的和的组合被排除在下一步之外，并且作为最终结果的结果，并且那些达到指定数量的组合不再增加。

int n = 6, m = 2; // n - sum, m - number of summands
Set<int[]> partition = IntStream.range(0, n)
        // prepare sets of arrays of summands
        .mapToObj(i -> IntStream.rangeClosed(1, n - i)
                .mapToObj(j -> new int[]{j})
                // Stream<TreeSet<int[]>>
                .collect(Collectors.toCollection(
                        // comparing the contents of two arrays
                        () -> new TreeSet<>(Arrays::compare))))
        // sequential summation of pairs of sets
        .reduce((set1, set2) -> set1.stream()
                // combinations of inner arrays
                .flatMap(arr1 -> {
                    // sum of the elements of the first array
                    int sum = Arrays.stream(arr1).sum();
                    // if the specified number is reached
                    if (sum == n) // and the number of summands is reached
                        if (arr1.length == m) // don't increase this combination
                            return Arrays.stream(new int[][]{arr1});
                        else return Stream.empty(); // drop this combination
                    // otherwise continue appending summands
                    return set2.stream() // drop the combinations that are greater
                            .filter(arr2 -> Arrays.stream(arr2).sum() + sum <= n)
                            .map(arr2 -> Stream.of(arr1, arr2)
                                    .flatMapToInt(Arrays::stream)
                                    .sorted().toArray()) // the sorted array
                            // drop too long combinations
                            .filter(arr2 -> arr2.length <= m);
                }) // set of arrays of combinations
                .collect(Collectors.toCollection( // two arrays that differ
                        // only in order are considered the same partition
                        () -> new TreeSet<>(Arrays::compare))))
        // otherwise an empty set of arrays
        .orElse(new TreeSet<>(Arrays::compare));

// output, the integer partition with restricted number of summands
partition.stream().map(Arrays::toString).forEach(System.out::println);

输出：

[1, 5]
[2, 4]
[3, 3]

另请参阅：构建有效地求和为数字的排列

于 2021-05-01T12:03:45.010 回答
0

既然您知道要使用多少位数，我相信您可以做到这一点。

首先你可以通过重复分区（n，2）来做到这一点。如果你想要 n = 3, m = 3，你可以只做 partition(n, 2)，然后为每个答案做 partition(k, 2)。

例子：

分区（6、3）：

分区（6、2）：

5 + 1、4 + 2、3 + 3、2 + 4、5 + 1

分区（5、2）：

4 + 1、3 + 2 ...

然后你只需将它们全部加在一起：

(4+1)+1, (3+2)+1, (2+3)+1, (1+4)+1, (3+1)+2...

并对它们进行排序（最大的数字在前）。

4+1+1, 4+1+1...

然后您可以删除所有重复项

Partition(n, 2) 将在 O(n) 中运行（因为您只需要循环到 n 并执行 x + (nx)）。您必须这样做的次数是某种 O(m)。并且排序可以在 n 中完成（因为你知道它都是整数）。所以我认为这将在 O(n*m) 中运行，这并不好，但它可能对你有用（如果 n 或 m 相当小）。

于 2015-10-02T12:50:26.750 回答
-2

这个问题似乎是子集和问题

NP problem这是所有解决方案的含义non-deterministic（即没有任何已知的有效算法）。

但是，您可以尝试一些启发式方法并以更有效的方式找到一些令人满意的结果。

于 2015-10-02T12:44:32.087 回答