计算将一排球放入盒子的方法数的算法

Question

我正在考虑一种计算划分球的方法数量的算法，下面是问题的设置:

1. 球与数字排成一行，即1,2,3,4,5，…N，我们不能改变球的顺序。
2. 我们想把球分组到盒子里，我们可以使用任意数量的盒子，但是盒子不能是空的。
3. 两组被认为是相同的，只有当他们在盒子的数量和相应的盒子的球相同。

分组球的一个例子是|1, 2|3, 4, 5|6|，它(明显)不同于|1, 2, 3|4, 5|6|

我想计算这些球分组的方法的个数。通常情况下，我会尝试强力搜索，但我甚至不知道从哪里开始。

下面是这个问题的一些有趣的扩展:

1. 我们有什么要求，在后一个盒子里的球的数量需要等于或大于前一个盒子?例如，我们可以处理|1|2, 3|4, 5|6, 7, 8|，但不能处理|1, 2, 3|4, 5|6, 7, 8|
2. 如果后一个盒子中的球的数量需要至少是前一个盒子的k倍，其中k是给定值并且至少为1，该怎么办?

Answer 1

这是整数组合的问题。
公式相当简单-有2^(n-1)组合。

第一个扩展是整数分区的问题。
没有已知的封闭公式。
欧拉五边形数定理的实现示例

对于第二个扩展，可以创建这样的递归函数(未检查，只是想法)

def partsktimes(x, current, k)
if x < 0:
return 0
if x == 0:
return 1
result = 0
for i in range(current*k, x+1):
result += partsktimes(x - i, i, k)