我正在尝试为 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://code.activestate.com/recipes/218332-generator-for-integer-partitions/
然而,我真正想要的是限制分区的数量。
比如说,# of partition k = 2,一个程序只需要显示5 = 4 + 1 = 3 + 2
,
如果 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
这会生成所有长度为 k
的 n
分区,每个分区按从小到大的顺序排列。
快速说明:通过cProfile
,使用生成器方法似乎比使用 faltru 的直接方法快得多,使用测试函数 lambda x,y: list(partitionfunc( x,y))
。在 n=50,k-5
的测试运行中,我的代码运行时间为 0.019 秒,而直接方法为 2.612 秒。
关于给定 k 个分区的 Python 整数分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18503096/