How to generate all possible sets of numbers for a fixed sum?
Lets say I have a fixed number ‘x’ and I want this number to be divided in a set of ‘y’ numbers, in such a way that sum of all the numbers in a set will be equal to ‘x’.
For example:
Total sum = ‘x’ = 30; Numbers in a set = ‘y’ = 3
So the output should be (30, 0, 0), (29, 1, 0), (28, 1, 1) and so on.
Kindly guide me.
yea that too, I am asking about all possible combinations.
Thanks a lot.
Hello,
This can quickly generate very large lists. Do you only want (30,0,0) and not (0,30,0) and (0,0,30) ?
I want all possible sets of combinations. Although for my work only one of these [ (30,0,0), (0,30,0) and (0,0,30) ] is required, but I would like to learn how to generate list of all possible combinations. Since it might lead to a very large list of combinations, I would try to limit that by using conditional formatting as per the requirement of work.
This can be done surprisingly easily with a python component.
Python comes with ‘batteries included’, for instance the itertools module has tools for combinations and permutations and we can use a set to get rid of duplicates. Here I use xrange to generate the numbers rather than range, to avoid holding all the numbers in memory together.
This is memory efficient: it only stores values which meet your requirements, but not computationally efficient: it checks every possible combination and only retains those which sum to x. If you need to handle large values of x and y then much more efficient algorithms exist.
from itertools import combinations_with_replacement
x = 30
y = 3
a = [i for i in combinations_with_replacement(xrange(x+1),y) if sum(i)==x]
print(a)
This gives
[(0, 0, 30), (0, 1, 29), (0, 2, 28), (0, 3, 27), (0, 4, 26), (0, 5, 25), (0, 6, 24), (0, 7, 23), (0, 8, 22), (0, 9, 21), (0, 10, 20), (0, 11, 19), (0, 12, 18), (0, 13, 17), (0, 14, 16), (0, 15, 15), (1, 1, 28), (1, 2, 27), (1, 3, 26), (1, 4, 25), (1, 5, 24), (1, 6, 23), (1, 7, 22), (1, 8, 21), (1, 9, 20), (1, 10, 19), (1, 11, 18), (1, 12, 17), (1, 13, 16), (1, 14, 15), (2, 2, 26), (2, 3, 25), (2, 4, 24), (2, 5, 23), (2, 6, 22), (2, 7, 21), (2, 8, 20), (2, 9, 19), (2, 10, 18), (2, 11, 17), (2, 12, 16), (2, 13, 15), (2, 14, 14), (3, 3, 24), (3, 4, 23), (3, 5, 22), (3, 6, 21), (3, 7, 20), (3, 8, 19), (3, 9, 18), (3, 10, 17), (3, 11, 16), (3, 12, 15), (3, 13, 14), (4, 4, 22), (4, 5, 21), (4, 6, 20), (4, 7, 19), (4, 8, 18), (4, 9, 17), (4, 10, 16), (4, 11, 15), (4, 12, 14), (4, 13, 13), (5, 5, 20), (5, 6, 19), (5, 7, 18), (5, 8, 17), (5, 9, 16), (5, 10, 15), (5, 11, 14), (5, 12, 13), (6, 6, 18), (6, 7, 17), (6, 8, 16), (6, 9, 15), (6, 10, 14), (6, 11, 13), (6, 12, 12), (7, 7, 16), (7, 8, 15), (7, 9, 14), (7, 10, 13), (7, 11, 12), (8, 8, 14), (8, 9, 13), (8, 10, 12), (8, 11, 11), (9, 9, 12), (9, 10, 11), (10, 10, 10)]
Search combination sum for other solutions:)
Dear Graham, thanks a lot for your solution. It has really helped with my work and saved me a lot of time. 