performance - 划分数字的算法

Question

给定一个正整数 X , 如何将其划分为 N零件，每个介于 A 之间和 B其中 A <= B也是正整数吗？即写

X = X_1 + X_2 + ... + X_N

哪里A <= X_i <= B和 X_i 的顺序没关系？

Answer 1

如果您想知道执行此操作的方法数，则可以使用生成函数。

本质上，您对 integer partitions 感兴趣. X 的整数分区是一种将X 写成正整数之和的方法。令p(n) 为n 的整数分区数。例如，如果 n=5 那么 p(n)=7 对应的分区:

5
4,1
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1

p(n) 的生成函数是

sum_{n >= 0} p(n) z^n = Prod_{i >= 1} ( 1 / (1 - z^i) )

这对你有什么作用？通过展开右侧并获取 z^n 的系数，您可以恢复 p(n)。不要担心乘积是无限的，因为您只会采用有限多项来计算 p(n)。事实上，如果这就是您想要的，那么只需截断乘积并在 i=n 处停止。

为什么会这样？记住这一点

1 / (1 - z^i) = 1 + z^i + z^{2i} + z^{3i} + ...

所以z^n的系数就是写法的数量

n = 1*a_1 + 2*a_2 + 3*a_3 +...

现在我将 a_i 视为 i 在 n 的分区中出现的次数。

这如何概括？事实证明，很容易。从上面的描述中，如果您只希望分区的部分在给定的集合 A 中，那么不要对所有 i >= 1 进行乘积，取乘积仅在 A 中的 i 上。设 p_A(n) 是 n 的整数分区数，其部分来自集合 A。然后

sum_{n >= 0} p_A(n) z^n = Prod_{i in A} ( 1 / (1 - z^i) )

同样，在此展开式中取 z^n 的系数可以解决您的问题。但我们可以更进一步，跟踪分区的部分数。为此，添加另一个占位符 q 以跟踪我们使用了多少部件。设 p_A(n,k) 是将 n 分成 k 部分的整数分区数，其中这些部分来自集合 A 。然后

sum_{n >= 0} sum_{k >= 0} p_A(n,k) q^k z^n = Prod_{i in A} ( 1 / (1 - q*z^i) )

所以取 q^k z^n 的系数给出 n 分成 k 部分的整数分区数集合A。

如何编写代码？ 生成函数方法实际上为您提供了一种算法，用于生成问题的所有解，以及一种从中统一采样的方法的解决方案集。一旦选择了n和k，右边的积就是有限的。