python:生成整数分区

Question

我需要生成给定整数的所有分区.
我发现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很容易.

值得注意的是,对于任何常量摊销时间算法,您实际对生成的对象所做的几乎肯定会主导生成它们的成本.例如,如果将所有分区存储在列表中,则管理此大型列表的内存所花费的时间将远远大于生成分区所花费的时间.

说,出于某种原因,您想要获取每个分区的产品.如果你对此采取一种天真的方法,那么所涉及的处理在部件数量上是线性的,而生成成本是恒定的.很难想到组合生成算法的应用,其中处理不会主导生成成本.因此,在实践中,使用更简单和更通用的ruleGen与sigma(x)= x和专用的accelAsc之间没有可测量的差异.

Answer 2

如果您要针对相同的输入重复使用此函数，那么缓存返回值仍然是值得的（如果您要在单独的运行中使用它，您可以将结果存储在文件中）。

如果您找不到明显更快的算法，那么应该可以通过将代码移动到 C 扩展中（这可能是使用cython最简单的），或者使用PyPy来将其速度加快一两个数量级CPython（PyPy 有其缺点 - 它尚不支持 Python 3，或一些常用的库，如 numpy 和 scipy）。

原因是，由于 python 是动态类型的，解释器可能花费大部分时间检查变量的类型 - 对于所有解释器来说，其中一个操作可能会变成x字符串，在这种情况下，像这样的表达式x + y将突然有了非常不同的含义。Cython 通过允许您将变量静态声明为整数来解决这个问题，而 PyPy 有一个即时编译器，可以最大限度地减少冗余类型检查。