找出所有加起来等于某个数字的数

Question

我想找到一种方法，来显示所有可能的整数组合，这些组合加起来等于一个给定的整数。例如，如果我要找出所有两个整数加起来等于5的组合，我会得到：

1, 4
2, 3

或者，如果是三个整数加起来等于6：

1, 1, 4
1, 2, 3
2, 2, 2

我只需要正整数，不包括0，而且组合的数量最多是15，最大数字是30。

我甚至不确定这个在数学上有没有专门的术语。它有点像因式分解，我想？

Answer 1

这些被称为整数的分区。其他人已经提供了相关链接来定义它们。

做这些事情的一个技巧是使用递归。比如说，我想找出所有不同的方法，把10分成正好三个整数的和，而且这些整数不能重复。

我们先看看这个和中最大的数。最大数能是10吗？不能，因为如果最大的数是10，那剩下的是什么呢？也就是说，10 - 10 = 0。结果发现，如果这个和中的最大数是7，那么剩下的部分要分成两个正整数就是3。而3只能以一种方式分成两个不同的整数。所以{7,2,1}就是这样的一个分区，而且这是唯一一个包含7这个大数的分区。

那6能作为最大的数吗？如果可以，那剩下的就是4。而4也只能以一种方式分成两个不同的整数，得到分区{6,3,1}。继续寻找，我们还可以找到其他的10的分区，比如{5,4,1}和{5,3,2}。没有其他的可能了。

关键是，这个操作可以很容易地定义为一个递归函数。如果编码得当，甚至可以使用记忆化的方法，避免重新计算我们之前见过的结果。

Answer 2

这里有一段代码片段，详细内容可以在这里找到：

from itertools import combinations, chain

def sum_to_n(n):
    'Generate the series of +ve integer lists which sum to a +ve integer, n.'
    from operator import sub
    b, mid, e = [0], list(range(1, n)), [n]
    splits = (d for i in range(n) for d in combinations(mid, i)) 
    return (list(map(sub, chain(s, e), chain(b, s))) for s in splits)

你可以这样使用它：

for p in sum_to_n(4):    
    print p

输出结果是：

[4]
[1, 3]
[2, 2]
[3, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[1, 1, 1, 1]

Answer 3

这里有一种解决这个问题的方法：

def sum_to_n(n, size, limit=None):
    """Produce all lists of `size` positive integers in decreasing order
    that add up to `n`."""
    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + size - 1) // size
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):
        for tail in sum_to_n(n - i, size - 1, i):
            yield [i] + tail

你可以这样使用它。

for partition in sum_to_n(6, 3):
    print partition

[2, 2, 2]
[3, 2, 1]
[4, 1, 1]