22

我正在尝试为 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

4

4 回答 4

24

我写了一个生成器解决方案

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，使用生成器方法似乎比使用 falsetru 的直接方法快得多，使用 test 函数lambda x,y: list(partitionfunc(x,y))。在 的测试运行中n=50,k-5，我的代码运行时间为 0.019 秒，而直接方法的运行时间为 2.612 秒。

于 2013-08-29T06:05:11.737 回答
6 
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)
于 2013-08-29T06:03:09.730 回答
5

首先，我要感谢大家的贡献。我来到这里需要一种算法来生成具有以下详细信息的整数分区：

将一个数字的分区生成为 EXACTLY 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)]
于 2017-03-25T10:40:46.010 回答
0

基于先前具有最大和最小约束的答案，我们可以将其优化得更好一些。例如，对于 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,)
于 2021-02-26T16:17:29.170 回答