Python分区函数需要优化

Question

在研究 project euler exercise (#78) 时，我了解到，为了划分一个数字，您可以创建一个幂级数。从该系列中，您可以展开并使用术语系数来获取划分特定数字的方法数。

从那里，我创建了这个小函数:

## I've included two arguments, 'lim' for the number you wish to partition and 'ways' a list of numbers you can use to partition that number 'lim'. ##

def stack(lim,ways):

    ## create a list of length of 'lim' filled with 0's. ##
    posi = [0] * (lim + 1)

    ## allow the posi[0] to be 1 ##
    posi[0] = 1

    ## double loop -- with the amount of 'ways'. ##
    for i in ways:
        for k in range(i, lim + 1):
            posi[k] += posi[k - i]

    ## return the 'lim' numbered from the list which will be the 'lim' coefficient. ##
    return posi[lim] 

>>> stack(100,[1,5,10,25,50,100])
>>> 293
>>> stack(100,range(1,100))
>>> 190569291
>>> stack(10000,range(1,10000))
>>> 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143L

这在相对较小的分区上运行良好，但不适用于此练习。有没有办法通过递归或更快的算法来加快速度？我读过一些地方，使用五边形数也是一种帮助分区的方法。

现在我不需要返回这个问题的实际数字，但是，检查它是否可以被 1000000 整除。

更新:我最终使用了 pentagonal number theorem .我将尝试使用 Craig Citro 发布的 Hardy-Ramanujan 渐近公式。

Answer 1

我最近没有亲自检查过这个事实，但“最快的分区算法”的称号可能仍然由 Sage 中的实现持有。可以看到the docs中提到了，或者更好的是直接跳到 the source code .如果您正在寻找有关计算此数字的方法的讨论，original thread导致这个实现绝对是有趣的。 source file for the implementation itself从关于代码的一些有用注释开始。