python:生成整数分区

Question

我需要生成所有 partitions给定整数。
我发现 Jerome Kelleher 提出的这个算法据称是最有效的算法:

def accelAsc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = 0
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2*x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

引用:http://homepages.ed.ac.uk/jkellehe/partitions.php

顺便说一句，它不是很有效。对于像 40 这样的输入，它几乎卡住了我的整个系统几秒钟，然后才给出它的输出。

如果它是一个递归算法，我会尝试用缓存函数或其他东西来装饰它以提高它的效率，但那样我不知道该怎么做。

关于如何加速这个算法，你有什么建议吗？或者你能建议我另一个，或者从头开始制作另一个的不同方法吗？

Answer 1

要直接生成合成，您可以使用以下算法:

def ruleGen(n, m, sigma):
    """
    Generates all interpart restricted compositions of n with first part
    >= m using restriction function sigma. See Kelleher 2006, 'Encoding
    partitions as ascending compositions' chapters 3 and 4 for details.
    """
    a = [0 for i in range(n + 1)]
    k = 1
    a[0] = m - 1
    a[1] = n - m + 1
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while sigma(x) <= y:
            a[k] = x
            x = sigma(x)
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

该算法非常通用，可以生成多种不同类型的分区和组合。对于您的情况，请使用

ruleGen(n, 1, lambda x: 1)

生成所有不受限制的组合。第三个参数称为限制函数，描述了您需要的组合/分区类型。该方法是有效的，因为当您对生成的所有作品进行平均时，生成每个作品所需的工作量是恒定的。如果你想让它在 python 中稍微快一点，那么很容易用 1 替换函数 sigma。

这里还值得注意的是，对于任何常数摊销时间算法，您实际对生成的对象执行的操作几乎肯定会支配生成它们的成本。例如，如果将所有分区存储在一个列表中，那么为这个大列表管理内存所花费的时间将远远大于生成分区所花费的时间。

比如说，出于某种原因，你想获取每个分区的乘积。如果您对此采取天真的方法，那么所涉及的处理在零件数量上是线性的，而生成成本是恒定的。很难想出一种组合生成算法的应用，其中处理不支配生成成本。因此，在实践中，使用带有 sigma(x) = x 的更简单和更通用的 ruleGen 与专门的 accelAsc 之间没有可衡量的区别。