9

我需要生成给定整数的所有分区。
我发现 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，我的整个系统几乎冻结了几秒钟，然后才给出它的输出。

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

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

4

4 回答 4

12

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

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 之间没有可测量的差异。

于 2012-05-01T14:21:09.647 回答
3

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

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

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

于 2012-04-20T10:55:50.130 回答
2

使用 n=75 进行测试我得到：

PyPy 1.8：

w:\>c:\pypy-1.8\pypy.exe pstst.py
1.04800009727 secs.

CPython 2.6：

w:\>python pstst.py
5.86199998856 secs.

Cython + mingw + gcc 4.6.2：

w:\pstst> python -c "import pstst;pstst.run()"
4.06399989128

我看不出与 Psyco 有什么不同（？）

运行函数：

def run():
    import time
    start = time.time()
    for p in accelAsc(75):
        pass
    print time.time() - start, 'secs.'

如果我更改 Cython 的 accelAsc 定义以开始：

def accelAsc(int n):
    cdef int x, y, k
    # no more changes..

我将 Cython 时间缩短到 2.27 秒。

于 2012-04-20T11:33:11.387 回答
0

我会说您的性能问题在其他地方。

我没有将它与其他方法进行比较，但它对我来说似乎很有效：

import time

start = time.time()
partitions = list(accelAsc(40))
print('time: {:.5f} sec'.format(time.time() - start))
print('length:', len(partitions))

给：

time: 0.03636 sec
length: 37338
于 2012-04-20T10:46:28.647 回答