是否有一个有效的整数分区算法，限制数量的部件？
我必须创建一个采用两个整数的方法，让它们为n和m ，并返回有多少种方法来求m正数来得到n 。 例如，像这个partition(6, 2)这样的方法调用应该返回3，因为有3种方法可能。 它们是5 + 1 4 + 2和3 + 3 。 顺便说一句， 4 + 2与2 + 4相同，因此该方法不应将它们视为两个不同的变化。 有人知道这个问题的解决方案吗？
更新： n和m不大于150。
递归算法
要计算具有m部分的整数n所有分区，递归算法是显而易见的选择。 对于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这样的序列都被它们的规范forms1+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, m的值存储在n - m, m n, m这两个三角形之间的平行四边形可以倾斜45°。 因此，高速缓存大小从(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) + "
"); // 1 document.write(partition(6, 2) + "
"); // 3 document.write(partition(9, 3) + "
"); // 7 document.write(partition(16, 4) + "
"); // 34 document.write(partition(150, 75) + "
"); // 8,118,264 // document.write(partition(150, 23)); // 1,901,740,434 (maximum for 150, takes > 10s)
您可以使用动态编程 。 令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) 。
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()); } private static long p(final long n, final long digitFrom, final long m, Stack 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; }
既然你知道要使用多少位数，我相信你可以做到这一点。
首先，您可以通过重复执行分区（n，2）来完成此操作。 如果你想要n = 3，m = 3，你可以只进行分区（n，2），然后对每个答案进行分区（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 ……
然后你可以删除所有重复项
分区（n，2）将在O（n）中运行（因为您只需要循环到n并执行x +（nx））。 您必须执行此操作的次数是某种O（m）。 排序可以在n中完成（因为你知道它是全部数字）。 所以我认为这将在O（n * m）中运行，这是不好的，但它可能对你有用（如果n或m相当小）。
这个问题似乎是SubSet Sum问题
它是NP problem意味着所有解决方案都是non-deterministic （即没有任何已知的有效算法）。
但是，您可以尝试一些启发式方法，并以更有效的方式找到一些令人满意的结果。