我正在尝试查找或开发适用于Python的整数分区代码。
仅供参考，整数分区将给定整数n表示为小于n的整数之和。例如，整数5可以表示为4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1
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/
但是，我真正想要的是限制分区数。
假设，分区 数k = 2，一个程序只需要显示5 = 4 + 1 = 3 + 2，
5 = 4 + 1 = 3 + 2
如果 k = 3，5 = 3 + 1 + 1 = 2 + 2 + 1
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每个分区的顺序从最小到最大。
n
k
简要说明一下：通过cProfile，似乎使用generator方法比使用testtru的falsetru直接方法要快得多lambda x,y: list(partitionfunc(x,y))。在的测试运行中n=50,k-5，我的代码运行了.019秒，而直接方法运行了2.612秒。
cProfile
lambda x,y: list(partitionfunc(x,y))
n=50,k-5
