How to iterate through array combinations with constant sum efficiently?

Question

I have an array and its length is X. Each element of the array has range 1 .. L. I want to iterate efficiently through all array combinations that has sum L.

Correct solutions for: L = 4 and X = 2

1 3
3 1
2 2

Correct solutions for: L = 5 and X = 3

1 1 3
1 3 1
3 1 1
1 2 2
2 1 2
2 2 1

The naive implementation is (no wonder) too slow for my problem (X is up to 8 in my case and L is up to 128).

Could anybody tell me how is this problem called or where to find a fast algorithm for the problem?

Thanks!

Answer 1

If I understand correctly, you're given two numbers 1 ≤ X ≤ L and you want to generate all sequences of positive integers of length X that sum to L.

(Note: this is similar to the integer partition problem, but not the same, because you consider 1,2,2 to be a different sequence from 2,1,2, whereas in the integer partition problem we ignore the order, so that these are considered to be the same partition.)

The sequences that you are looking for correspond to the combinations of X − 1 items out of L − 1. For, if we put the numbers 1 to L − 1 in order, and pick X − 1 of them, then the lengths of intervals between the chosen numbers are positive integers that sum to L.

For example, suppose that L is 16 and X is 5. Then choose 4 numbers from 1 to 15 inclusive:

Add 0 at the beginning and 16 at the end, and the intervals are:

and 3 + 4 + 1 + 6 + 2 = 16 as required.

So generate the combinations of X − 1 items out of L − 1, and for each one, convert it to a partition by finding the intervals. For example, in Python you could write:

from itertools import combinations

def partitions(n, t):
    """
    Generate the sequences of `n` positive integers that sum to `t`.
    """
    assert(1 <= n <= t)
    def intervals(c):
        last = 0
        for i in c:
            yield i - last
            last = i
        yield t - last
    for c in combinations(range(1, t), n - 1):
        yield tuple(intervals(c))

>>> list(partitions(2, 4))
[(1, 3), (2, 2), (3, 1)]
>>> list(partitions(3, 5))
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

There are (L − 1)! / (X − 1)!(L − X)! combinations of X − 1 items out of L − 1, so the runtime of this algorithm (and the size of its output) is exponential in L. However, if you don't count the output, it only needs O(L) space.

With L = 128 and X = 8, there are 89,356,415,775 partitions, so it'll take a while to output them all!

(Maybe if you explain why you are computing these partitions, we might be able to suggest some way of meeting your requirements without having to actually produce them all.)