Return a sequence of a variable length whose summation is equal to a given integer

Question

In the form f(x,y,z) where x is a given integer sum, y is the minimum length of the sequence, and z is the maximum length of the sequence. But for now let's pretend we're dealing with a sequence of a fixed length, because it will take me a long time to write the question otherwise.

So our function is f(x,r) where x is a given integer sum and r is the length of a sequence in the list of possible sequences.

For x = 10, and r = 2, these are the possible combinations:

1 + 9
2 + 8
3 + 7
4 + 6
5 + 5

Let's store that in Python as a list of pairs:

[(1,9), (2,8), (3,7), (4,6), (5,5)]

So usage looks like:

>>> f(10,2)
[(1,9), (2,8), (3,7), (4,6), (5,5)]

Back to the original question, where a sequence is return for each length in the range (y,x). I the form f(x,y,z), defined earlier, and leaving out sequences of length 1 (where y-z == 0), this would look like:

>>> f(10,1,3)
[{1: [(1,9), (2,8), (3,7), (4,6), (5,5)],
  2: [(1,1,8), (1,2,7), (1,3,6) ... (2,4,4) ...],
  3: [(1,1,1,7) ...]}]

So the output is a list of dictionaries where the value is a list of pairs. Not exactly optimal.

So my questions are:

1. Is there a library that handles this already?
2. If not, can someone help me write both of the functions I mentioned? (fixed sequence length first)?
3. Because of the huge gaps in my knowledge of fairly trivial math, could you ignore my approach to integer storage and use whatever structure the makes the most sense?

Sorry about all of these arithmetic questions today. Thanks!

Answer 1

The problem is known as Integer Partitions, and has been widely studied.

Here you can find a paper comparing the performance of several algorithms (and proposing a particular one), but there are a lot of references all over the Net.

Answer 2

The itertools module will definately be helpful as we're dealing with premutations - however, this looks suspiciously like a homework task...

Edit: Looks like fun though, so I'll do an attempt.

Edit 2: This what you want?

from itertools import combinations_with_replacement
from pprint import pprint

f = lambda target_sum, length: [sequence for sequence in combinations_with_replacement(range(1, target_sum+1), length) if sum(sequence) == target_sum]

def f2(target_sum, min_length, max_length):
    sequences = {}
    for length in range(min_length, max_length + 1):
        sequence = f(target_sum, length)
        if len(sequence):
            sequences[length] = sequence
    return sequences

if __name__ == "__main__":
    print("f(10,2):")
    print(f(10,2))
    print()
    print("f(10,1,3)")
    pprint(f2(10,1,3))

Output:

f(10,2):
[(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)]

f(10,1,3)
{1: [(10,)],
 2: [(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)],
 3: [(1, 1, 8),
     (1, 2, 7),
     (1, 3, 6),
     (1, 4, 5),
     (2, 2, 6),
     (2, 3, 5),
     (2, 4, 4),
     (3, 3, 4)]}

Answer 3

I just wrote a recursive generator function, you should figure out how to get a list out of it yourself...

def f(x,y):
    if y == 1:
        yield (x, )
    elif y > 1:
        for head in range(1, x-y+2):
            for tail in f(x-head, y-1):
                yield tuple([head] + list(tail))

def f2(x,y,z):
    for u in range(y, z+1):
        for v in f(x, u):
            yield v

EDIT: I just see it is not exactly what you wanted, my version also generates duplicates where only the ordering differs. But you can simply filter them out by ordering all results and check for duplicate tuples.