生成数字的分区

Question

我需要一种算法来生成所有可能的正数分区，然后我想到了一个算法（作为答案发布），但这是指数时间。该算法应返回所有可能的方式，以小于或等于其自身的正数之和表示一个数字。因此，例如对于数字5，结果将是：54 + 13 + 23 + 1 + 12 + 2 + 12 + 1 + 1 + 11 + 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):

    try:

        return q[n]

    except:

        pass

    result = [[n]]

    for i in range(1, n):

        a = n-i

        R = decompose(i)

        for r in R:

            if r[0] <= a:

                result.append([a] + r)

    q[n] = result

    return result

 

>>> decompose(5)

[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]