数字分区：仅具有确定循环的非递归算法

Question

我正在尝试生成非负整数的数字分区集。该网站上也有多种解决方案，例如 Number of Ways to Partition a Number in Python:

def P(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    for p in P(n-1):        
        p.append(1)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p

但是这些解决方案使用递归或不确定循环（do-while 循环）。

我想用一个迭代解决方案来做到这一点，其中所有循环都是“确定的”（循环开始时已知的迭代次数）。但我不明白如何做到这一点。鉴于Wikipedia说“没有已知配分函数的封闭式表达式”，这是否可能？

Answer 1

下面我在 Python 中提供了一个仅使用“确定”

for

循环的函数，即在循环开始之前已知的范围内进行迭代的循环。

它利用了Wikipedia - Triangle of Partition Numbers中提到的递归关系：

...将 𝑛 分割成 𝑘 块，用 𝑝_𝑘(𝑛) 计数，可以通过将一块大小为 1 的块添加到将 𝑛−1 分割成 𝑘−1 块（用 𝑝 _{计数）来形成𝑘−1}(𝑛−1)，或者将 𝑛−𝑘 划分为 𝑘 块，每块增加 1 个，并按 𝑝_𝑘(𝑛−𝑘) 计数。

def make_partitions(n):
    # all numbers up to n, represented as a partition with just one member
    dp = [[[total]] for total in range(0, n + 1)]
    dp[0] = []
    # the last of these is one possible partition of n:
    result = dp[-1][:]

    # for increasing size of the partitions (i.e. count of terms)
    for size in range(2, n + 1):
        prev = dp[size - 1]
        dp[size - 1] = []
        # generate partitions using already known partitions
        for total in range(size, n + 1):
            prev, dp[total] = dp[total], (
                [partition + [1] for partition in prev] + 
                [
                    [val+1 for val in partition]
                    for partition in dp[total-size]
                ]
            )
        result.extend(dp[-1])
    return result

例如，调用

make_partitions(9)

将返回此列表：

[
    [9],
    [8, 1],
    [7, 2],
    [6, 3],
    [5, 4],
    [7, 1, 1],
    [6, 2, 1],
    [5, 3, 1],
    [4, 4, 1],
    [5, 2, 2],
    [4, 3, 2],
    [3, 3, 3],
    [6, 1, 1, 1],
    [5, 2, 1, 1],
    [4, 3, 1, 1],
    [4, 2, 2, 1],
    [3, 3, 2, 1],
    [3, 2, 2, 2],
    [5, 1, 1, 1, 1],
    [4, 2, 1, 1, 1],
    [3, 3, 1, 1, 1],
    [3, 2, 2, 1, 1],
    [2, 2, 2, 2, 1],
    [4, 1, 1, 1, 1, 1],
    [3, 2, 1, 1, 1, 1],
    [2, 2, 2, 1, 1, 1],
    [3, 1, 1, 1, 1, 1, 1],
    [2, 2, 1, 1, 1, 1, 1],
    [2, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1]
]