是否有一种有效的整数分区算法，零件数量有限？
Is there an efficient algorithm for integer partitioning with restricted number of parts?
我必须创建一个接受两个整数的方法，让它们成为 n 和 m，并且 return 有多少种方法可以求和 m正数得到 n。
例如，像这样的方法调用 partition(6, 2) 应该 return 3 因为有 3 种可能的方法。它们是 5 + 1、4 + 2 和 3 + 3。顺便说一句，4 + 2 与 2 + 4 相同，因此该方法不应将它们视为两个不同的变体。
有人知道解决问题的方法吗？
已更新：n 和 m 不大于 150。
这个问题好像是SubSet Sum Problem
它是一个 NP problem，这意味着所有的解决方案都是 non-deterministic（即没有任何已知的有效算法）。
但是您可以尝试一些启发式方法，并以更有效的方式找到一些令人满意的结果。
既然你知道要使用多少位数，我相信你可以做到。
首先，您可以通过重复执行 partition(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 + (n-x)）。您必须执行此操作的次数是某种 O(m)。排序可以在 n 中完成（因为你知道它都是整数）。所以我认为这将在 O(n*m) 中 运行，这不是很好，但它可能对你有用（如果 n 或 m 相当小）。
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;
}
您可以使用 dynamic programming。设f[n][m][k]为m个非递减正数的分区数，使得总和为n，最后一个为k。然后你可以很容易地看到更新步骤是：
f[n][m][k] → f[n+l][m+1][l] for every l≥ k
要得到f[n][m]，意思是所有分区的个数独立于最后一个数，最后把所有k相加即可。复杂度为 O(n^2 m).
递归算法
要计算整数 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；有了记忆，只需要 15,163 次递归。
下图显示了这种情况下的缓存读取和写入。灰色单元未使用，白色单元已写入但从未读取。共有 2042 次写入和 12697 次读取。
减少缓存大小
您会注意到左上角和右下角的三角形从未使用过； m 的值越接近 n，未使用的区域就越大。为了避免 space 的这种浪费，这两个三角形之间的平行四边形可以倾斜 45°，方法是将 n, m 的值存储在 n - m, m 中。缓存大小因此从(n - 1) * (m - 1)减小到(n - m) * (m - 1)，而n,m <= 150的最坏情况不再是149 * 149 = 22201，而是75 * 74 = 5550，不到25%尺寸。
代码示例 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' s最大安全整数为253-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
映射和减少方法
可以先准备被加数序列，然后依次对它们进行处理，一步步得到笛卡尔积。
作为加数序列，您可以将 TreeMap<int[]> 与比较器一起使用，该比较器比较两个 已排序 数组的内容，以消除重复组合，例如 4+2 和 2+4。如果要保留这些组合，可以使用二维数组 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]
另请参阅：
我必须创建一个接受两个整数的方法，让它们成为 n 和 m，并且 return 有多少种方法可以求和 m正数得到 n。
例如，像这样的方法调用 partition(6, 2) 应该 return 3 因为有 3 种可能的方法。它们是 5 + 1、4 + 2 和 3 + 3。顺便说一句，4 + 2 与 2 + 4 相同，因此该方法不应将它们视为两个不同的变体。
有人知道解决问题的方法吗？
已更新：n 和 m 不大于 150。
这个问题好像是SubSet Sum Problem
它是一个 NP problem，这意味着所有的解决方案都是 non-deterministic（即没有任何已知的有效算法）。
但是您可以尝试一些启发式方法，并以更有效的方式找到一些令人满意的结果。
既然你知道要使用多少位数，我相信你可以做到。
首先，您可以通过重复执行 partition(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 + (n-x)）。您必须执行此操作的次数是某种 O(m)。排序可以在 n 中完成（因为你知道它都是整数）。所以我认为这将在 O(n*m) 中 运行，这不是很好，但它可能对你有用（如果 n 或 m 相当小）。
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;
}
您可以使用 dynamic programming。设f[n][m][k]为m个非递减正数的分区数，使得总和为n，最后一个为k。然后你可以很容易地看到更新步骤是：
f[n][m][k] → f[n+l][m+1][l] for every l≥ k
要得到f[n][m]，意思是所有分区的个数独立于最后一个数，最后把所有k相加即可。复杂度为 O(n^2 m).
递归算法
要计算整数 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；有了记忆，只需要 15,163 次递归。
下图显示了这种情况下的缓存读取和写入。灰色单元未使用，白色单元已写入但从未读取。共有 2042 次写入和 12697 次读取。
减少缓存大小
您会注意到左上角和右下角的三角形从未使用过； m 的值越接近 n，未使用的区域就越大。为了避免 space 的这种浪费，这两个三角形之间的平行四边形可以倾斜 45°，方法是将 n, m 的值存储在 n - m, m 中。缓存大小因此从(n - 1) * (m - 1)减小到(n - m) * (m - 1)，而n,m <= 150的最坏情况不再是149 * 149 = 22201，而是75 * 74 = 5550，不到25%尺寸。
代码示例 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' s最大安全整数为253-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
映射和减少方法
可以先准备被加数序列，然后依次对它们进行处理，一步步得到笛卡尔积。
作为加数序列，您可以将 TreeMap<int[]> 与比较器一起使用，该比较器比较两个 已排序 数组的内容，以消除重复组合，例如 4+2 和 2+4。如果要保留这些组合，可以使用二维数组 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]
另请参阅：