数字分区算法

Question

Python 或 C++ 中是否有任何算法可以显示或作用于数字分区集 使用非递归且无不确定循环（无 do-while 循环）的非负整数？

文献使用了我们无法使用的递归和 do-while 循环。

Answer 1

这是 Python 中的一个函数，仅使用“确定”

for

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

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]
]