计算分区数量的算法？

Question

最近，我遇到了将不同宽度尺寸的小容器水平均匀分散到巨大宽度尺寸容器中的问题。有数百万个巨型容器和数十亿个小型容器。我需要想出一个算法。我将问题简化为以下问题:

让我们使用 Process(Number,Parts) 为例:

数字4可以通过3种方式分割成2部分(不包括0)。 处理(4,2)=3:

1 + 3
3 + 1
2 + 2

同样，数字4可以通过两种方式分成3部分Process(4,3)=2:

1 + 1 + 2
2 + 1 + 1
1 + 2 + 1

显然Process(4,4)=1

(不包括Process(4,1)=1，因为它是4+0，其中不应取0考虑在内)

不知道有没有办法计算

SuperProcess(4)=Process(4,2)+Process(4,3)+Process(4,4)=7

时间复杂度较低？或者换句话说，更快!!

特别是当请求要计算时:SuperProcess(1209)

是否有某种数学方法而不是粗略的循环来执行此计算？

Answer 1

SuperProcess(n) 被称为 number of compositions of an integer而不是number of partitions其中包含相同加数的和被认为是相同的，与顺序无关。

正整数 n 恰好有 2**(n-1)-1 个组合，不包括只有一个加数的和。

因此，计算 SuperProcess(n) 的最佳算法就是计算表达式 2**(n-1)-1，这可以在 Theta(n)时间。

如果您想枚举所有组合，可以使用递归函数来完成，该函数将当前位置的整数m的每个值1...n总和，然后使用 n-m 递归调用自身以获取下一个位置，并在 0 参数处停止。

枚举算法将花费 Theta(n 2**n) 时间，这是最佳的，因为这是显式保存/打印所有组合所需的时间。