Python get all numbers that add up to a number

Question

I'm trying to find a way to display all the possible sets of X integers that add up to a given integer. for example to get all 2 integer sets that make 5 I would have:

1, 4
2, 3

Or for 3 integers that make 6:

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

I only need whole numbers not including 0 and it only needs to work on up to about 15 in a set and 30 max. number.

I'm not even sure if this has a term mathematically, its similar to factorisation I guess?

Answer 1

http://en.wikipedia.org/wiki/Partition_(number_theory)

http://mathworld.wolfram.com/Partition.html

http://code.activestate.com/recipes/218332/

Answer 2

There's a snippet here:

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)

Use it like this:

for p in sum_to_n(4):    
    print p

Outputs:

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

Answer 3

These are called partitions of the integer in question. Others have provided links to define them.

A trick to do these things is often to do them recursively. For example, suppose I wanted to form all distinct ways to build 10 as the sum of exactly three integers, none of which appears more than once.

Look at the largest possible component in that sum. Can it be 10? No, since if the largest component is a 10, then what remains? I.e., 10 - 10 = 0. It turns out that if the largest element in the sum is a 7, then what remains, to be partitioned into a sum of two positive integers is 3. And we can break 3 into a sum of two distinct integers in exactly one way. So {7,2,1} is such a partition, and the only partition that involves an element as large as 7.

Can 6 be used as the largest element? If so, then we would have 4 remaining. And we can break 4 in exactly one way, to yield the partition {6,3,1}. Further searching will yield other partitions of 10 as {5,4,1}, {5,3,2}. No others can exist.

The point is, this operation can easily be defined as a recursive function. With careful coding, one might even use memoization, to avoid recomputing that which we have seen before.

Answer 4

Here is one way to solve this problem:

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

You can use it like this.

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

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