我正在尝试为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/
然而，我真正想要的是限制分区的数量。
比方说，分区#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
这生成具有长度CCD_ 5的CCD_。
只需简单说明：通过cProfile，使用生成器方法似乎比使用falstru的直接方法（使用测试函数lambda x,y: list(partitionfunc(x,y))）快得多。在n=50,k-5的测试运行中，我的代码运行时间为.019秒，而直接方法的运行时间为2.612秒。
def part(n, k):
def _part(n, k, pre):
if n <= 0:
return []
if k == 1:
if n <= pre:
return [[n]]
return []
ret = []
for i in range(min(pre, n), 0, -1):
ret += [[i] + sub for sub in _part(n-i, k-1, i)]
return ret
return _part(n, k, n)
示例：
>>> part(5, 1)
[[5]]
>>> part(5, 2)
[[4, 1], [3, 2]]
>>> part(5, 3)
[[3, 1, 1], [2, 2, 1]]
>>> part(5, 4)
[[2, 1, 1, 1]]
>>> part(5, 5)
[[1, 1, 1, 1, 1]]
>>> part(6, 3)
[[4, 1, 1], [3, 2, 1], [2, 2, 2]]
更新
使用记忆：
def part(n, k):
def memoize(f):
cache = [[[None] * n for j in xrange(k)] for i in xrange(n)]
def wrapper(n, k, pre):
if cache[n-1][k-1][pre-1] is None:
cache[n-1][k-1][pre-1] = f(n, k, pre)
return cache[n-1][k-1][pre-1]
return wrapper
@memoize
def _part(n, k, pre):
if n <= 0:
return []
if k == 1:
if n <= pre:
return [(n,)]
return []
ret = []
for i in xrange(min(pre, n), 0, -1):
ret += [(i,) + sub for sub in _part(n-i, k-1, i)]
return ret
return _part(n, k, n)
首先我要感谢大家的贡献。我来到这里需要一个生成整数分区的算法，详细信息如下：
将一个数字的分区生成精确的k个部分，但也具有MINIMUM和MAXIMUM约束
因此，我修改了"；Snakes and Coffee"；以适应这些新要求：
def partition_min_max(n, k, l, m):
''' n is the integer to partition, k is the length of partitions,
l is the min partition element size, m is the max partition element size '''
if k < 1:
raise StopIteration
if k == 1:
if n <= m and n>=l :
yield (n,)
raise StopIteration
for i in range(l,m+1):
for result in partition_min_max(n-i, k-1, i, m):
yield result+(i,)
>>> x = list(partition_min_max(20 ,3, 3, 10 ))
>>> print(x)
>>> [(10, 7, 3), (9, 8, 3), (10, 6, 4), (9, 7, 4), (8, 8, 4), (10, 5, 5), (9, 6, 5), (8, 7, 5), (8, 6, 6), (7, 7, 6)]
基于前面的最大和最小约束的答案，我们可以对其进行更好的优化。对于k=16，n=2048和m=128的例子，只有一个这样的分区满足约束（128+128+…+128）。但是代码搜索不必要的分支以寻找可以修剪的答案。
def partition_min_max(n,k,l,m):
#n is the integer to partition, k is the length of partitions,
#l is the min partition element size, m is the max partition element size
if k < 1:
return
if k == 1:
if n <= m and n>=l :
yield (n,)
return
if (k*128) < n: #If the current sum is too small to reach n
return
if k*1 > n:#If current sum is too big to reach n
return
for i in range(l,m+1):
for result in partition_min_max(n-i,k-1,i,m):
yield result+(i,)