Python分区功能需要优化

在研究project euler exercise (#78)时，我了解到，为了对数字进行分区，您可以创建一个幂级数。从该系列中，您可以扩展并使用术语系数来获取划分特定数字的方法数量。Python分区功能需要优化

从那里，我创造了这个小功能：

## 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渐近公式。

来源

2012-07-30 tijko

是否有可能提供该功能的输入示例，并且它是输出？既是一个快速案例，又是一个“太长”的案例？ – 2012-07-30 01:01:39

@JoshSmeaton肯定的事情。 – tijko 2012-07-30 01:04:33

我最近没有亲自检查过这个事实，但是“最快分区算法”的标题可能仍然是在Sage中实现的。您可以在the docs中看到它，或者更好，然后直接跳至the source code。如果你正在寻找关于计算这个数字的方法的讨论，导致这个实现的original thread肯定是有趣的。 source file for the implementation itself从关于代码的一些有用的评论开始。

来源

2012-07-30 05:11:57

这些是一些很棒的链接，他们将是一个非常有用的资源谢谢。我一定误解了，我不认为Hardy-Ramanujan渐近公式对于这个目的是准确的甚至准确的。我认为它只能给出一个近似值。我会查看是否可以使用[this]（http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas）编写我自己的函数。 – tijko 2012-07-30 18:52:55

Python分区功能需要优化

回答

相关问题