Print all possible distribution of sums of n into m spaces

Question

For example, wanting a sum of 3 into 4 spaces would be:

or sum of 3 into 2 spaces would be:

Hm... That's an algorithical problem, not a python-specific – Oct 14 '18 at 21:10 — , Oct 14 '18 at 21:10

Olivier Melançon · Accepted Answer · 2018-10-14T23:41:47.710

4

The sequences you are looking for are called compositions.

Finding a composition of a number n is equivalent to selecting indices in an interval from 0 to n. You recover the composition by getting the distance between consecutive selected indices.

Example

Given the number n = 3, we want a composition of length 4.

The first two indices must be 0 and 3 since this is our range. We then select three more indices in the interval [0, 1, 2, 3] to produce exactly 4 gaps.

[0, 1, 2, 3]
 ^     ^  ^
       ^  ^

We thus selected 0, 2, 2, 3, 3. We recover the composition by getting the distance between consecutive indices. That is [2, 0, 1, 0].

This corresponds to taking a combination with replacement of numbers from 0 to 3. We can thus use itertools.combinations_with_replacement and translate each such combination into the corresponding composition.

Code

def compositions(sum_, n):
    for indices in combinations_with_replacement(range(sum_ + 1), n - 1):
        yield [b - a for a, b in zip([0, *indices], [*indices, sum_])]

print(*compositions(3, 4))

Output

[0, 0, 0, 3]
[0, 0, 1, 2]
[0, 0, 2, 1]
[0, 0, 3, 0]
[0, 1, 0, 2]
[0, 1, 1, 1]
[0, 1, 2, 0]
[0, 2, 0, 1]
[0, 2, 1, 0]
[0, 3, 0, 0]
[1, 0, 0, 2]
[1, 0, 1, 1]
[1, 0, 2, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 2, 0, 0]
[2, 0, 0, 1]
[2, 0, 1, 0]
[2, 1, 0, 0]
[3, 0, 0, 0]

edited Oct 14 '18 at 23:41

answered Oct 14 '18 at 21:32

Olivier Melançon

21,584
4
41
73

Oooo now this I like over your first response, alot... this is pretty – vash_the_stampede Oct 14 '18 at 21:45
Glad you do! I even added some explanation of the mechanic behind it – Olivier Melançon Oct 14 '18 at 21:50
I don't understand where the 'implicit' index 4 comes into play. It is never selected, and the distance to it is never used. – m69's been on strike for years Oct 14 '18 at 22:17
2

@m69 You might want to refresh, I originally made a mistake in the explanation – Olivier Melançon Oct 14 '18 at 22:18
1

You may enjoy my partition code [here](https://stackoverflow.com/a/40220262/4014959), and check out the linked article by Jerome Kelleher. – PM 2Ring Oct 14 '18 at 22:58

score 1 · Answer 2 · answered Oct 14 '18 at 21:13

1

Using itertools.product and filter create all the possibilities and then filter the ones whose sum is 3

from itertools import product

lst = [0, 1, 2, 3]
print(list(filter(lambda x: sum(x) == 3, product(lst, repeat = 4))))
print(list(filter(lambda x: sum(x) == 3, product(lst, repeat = 2))))

answered Oct 14 '18 at 21:13

vash_the_stampede

4,590
1
8
20

Although, this traveses *a lot* of combinations that do not sum to 3 – Olivier Melançon Oct 14 '18 at 21:36
@OlivierMelançon I know and Martijn said something to me about a similar problem, the thought kept popping up in my head, how would work around that fact? – vash_the_stampede Oct 14 '18 at 21:37
I actually figured out the correct abstraction, you must use combinations with replacements to iter over exactly the partitions you want. See my answer – Olivier Melançon Oct 14 '18 at 21:44

Print all possible distribution of sums of n into m spaces

2 Answers2

Example

Code

Output