我正在尝试寻找或开发Python 的整数分区代码。
仅供参考,整数分区将给定整数 n 表示为小于 n 的整数之和。例如,整数5可以表示为4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1
我为此找到了许多解决方案。http://homepages.ed.ac.uk/jkellehe/partitions.php http://homepages.ed.ac.uk/jkellehe/partitions.php and http://code.activestate.com/recipes/218332-generator-for-integer-partitions/ http://code.activestate.com/recipes/218332-generator-for-integer-partitions/
然而,我真正想要的是限制分区的数量。
比如说,分区#k= 2、一个程序只需要显示5 = 4 + 1 = 3 + 2
,
if k = 3, 5 = 3 + 1 + 1 = 2 + 2 + 1
我写了一个生成器解决方案
def partitionfunc(n,k,l=1):
'''n is the integer to partition, k is the length of partitions, l is the min partition element size'''
if k < 1:
raise StopIteration
if k == 1:
if n >= l:
yield (n,)
raise StopIteration
for i in range(l,n+1):
for result in partitionfunc(n-i,k-1,i):
yield (i,)+result
这会生成以下所有分区n
与长度k
每一项都按从小到大的顺序排列。
简单说明一下:通过cProfile
,看来使用generator方法比使用falsetru的直接方法要快很多,使用test函数lambda x,y: list(partitionfunc(x,y))
。在试运行中n=50,k-5
,我的代码运行时间为 0.019 秒,而直接方法则为 2.612 秒。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)