Search code examples
pythonarrayspython-3.xpython-itertools

How to get all combination for a given sum with a given number of elements

I have a list of list of floats like this

numbers = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]

I want a python code that can generate all possible combinations for given sum (=1) and a given number of element, for example :

numbers = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]
sum = 1 
number of elements = 3

outputs :

[(0.1, 0.1, 0.8), (0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.1, 0.5, 0.4), (0.1, 0.6, 0.3), (0.1, 0.7, 0.2), (0.1, 0.8, 0.1), (0.2, 0.1, 0.7), (0.2, 0.2, 0.6), (0.2, 0.3, 0.5), (0.2, 0.4, 0.4), (0.2, 0.5, 0.3), (0.2, 0.6, 0.2), (0.2, 0.7, 0.1), (0.3, 0.1, 0.6), (0.3, 0.2, 0.5), (0.3, 0.3, 0.4), (0.3, 0.4, 0.3), (0.3, 0.5, 0.2), (0.3, 0.6, 0.1), (0.4, 0.1, 0.5), (0.4, 0.2, 0.4), (0.4, 0.3, 0.3), (0.4, 0.4, 0.2), (0.4, 0.5, 0.1), (0.5, 0.1, 0.4), (0.5, 0.2, 0.3), (0.5, 0.3, 0.2), (0.5, 0.4, 0.1), (0.6, 0.1, 0.3), (0.6, 0.2, 0.2), (0.6, 0.3, 0.1), (0.7, 0.1, 0.2), (0.7, 0.2, 0.1), (0.8, 0.1, 0.1)]
Solution

  • A very simple approach is to use itertools.combinations to generate all the possible combinations, and select those that produce the desired sum.

    >>> import itertools
>>> numbers = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]
>>> target_sum = 1
>>> number = 3
>>> [c for c in itertools.combinations(numbers, number) if sum(c) == target_sum]
[(0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.2, 0.3, 0.5)]

    If you want all the possible different orderings as distinct solutions, use itertools.permutations instead:

    >>> [c for c in itertools.permutations(numbers, number) if sum(c) == target_sum]
[(0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.1, 0.5, 0.4), (0.1, 0.6, 0.3), (0.1, 0.7, 0.2), (0.2, 0.1, 0.7), (0.2, 0.3, 0.5), (0.2, 0.5, 0.3), (0.3, 0.1, 0.6), (0.3, 0.2, 0.5), (0.3, 0.5, 0.2), (0.4, 0.1, 0.5), (0.4, 0.5, 0.1), (0.5, 0.1, 0.4), (0.5, 0.2, 0.3), (0.5, 0.3, 0.2), (0.5, 0.4, 0.1), (0.6, 0.1, 0.3), (0.7, 0.1, 0.2)]

    If you want to be able to use each element more than once, use itertools.combinations_with_replacement:

    >>> [c for c in itertools.combinations_with_replacement(numbers, number) if sum(c) == target_sum]
[(0.1, 0.1, 0.8), (0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.2, 0.2, 0.6), (0.2, 0.3, 0.5), (0.2, 0.4, 0.4), (0.3, 0.3, 0.4)]

    If you want to use elements multiple times and get all the possible orderings, use itertools.product:

    >>> [c for c in itertools.product(numbers, repeat=number) if sum(c) == target_sum]
[(0.1, 0.1, 0.8), (0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.1, 0.5, 0.4), (0.1, 0.6, 0.3), (0.1, 0.7, 0.2), (0.1, 0.8, 0.1), (0.2, 0.1, 0.7), (0.2, 0.2, 0.6), (0.2, 0.3, 0.5), (0.2, 0.4, 0.4), (0.2, 0.5, 0.3), (0.2, 0.6, 0.2), (0.3, 0.1, 0.6), (0.3, 0.2, 0.5), (0.3, 0.3, 0.4), (0.3, 0.4, 0.3), (0.3, 0.5, 0.2), (0.4, 0.1, 0.5), (0.4, 0.2, 0.4), (0.4, 0.3, 0.3), (0.4, 0.4, 0.2), (0.4, 0.5, 0.1), (0.5, 0.1, 0.4), (0.5, 0.2, 0.3), (0.5, 0.3, 0.2), (0.5, 0.4, 0.1), (0.6, 0.1, 0.3), (0.6, 0.2, 0.2), (0.7, 0.1, 0.2), (0.8, 0.1, 0.1)]