生成数字的分区

Question

我需要一种算法来生成所有可能的正数分区，然后我想到了一个算法（作为答案发布），但这是指数时间。

该算法应返回所有可能的方式，以小于或等于其自身的正数之和表示一个数字。因此，例如对于数字5，结果将是：

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

所以我的问题是：有没有更有效的算法呢？

编辑：问题的标题是“一个数字的总和分解”，因为我真的不知道这叫什么。ShreevatsaR指出它们被称为“分区”，因此我相应地编辑了问题标题。

Answer 1

它称为分区。[另请参阅Wikipedia：分区（数论）。]分区的数量p（n）呈指数增长，因此生成所有分区的所有操作都必须花费指数时间。也就是说，您可以做得比代码更好。请参见David Eppstein在Python Algorithms and Data Structures中的此版本或其更新版本。

Answer 2

这是我在Python中的解决方案（指数时间）：q = { 1: [[1]] }def decompose(n):&nbsp; &nbsp; try:&nbsp; &nbsp; &nbsp; &nbsp; return q[n]&nbsp; &nbsp; except:&nbsp; &nbsp; &nbsp; &nbsp; pass&nbsp; &nbsp; result = [[n]]&nbsp; &nbsp; for i in range(1, n):&nbsp; &nbsp; &nbsp; &nbsp; a = n-i&nbsp; &nbsp; &nbsp; &nbsp; R = decompose(i)&nbsp; &nbsp; &nbsp; &nbsp; for r in R:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if r[0] <= a:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.append([a] + r)&nbsp; &nbsp; q[n] = result&nbsp; &nbsp; return result&nbsp;>>> decompose(5)[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]