How to get all possible combinations with constraints?

Question

I need to get all possible 5 combinations from a list with the following constraints:

Combinations must include repetitions.
The sum of all numbers is equal to 1.

Here is my code so far:

    number = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]
    comb = [c for c in itertools.product(number, repeat=5) if  c[0] + c[1] + c[2] + c[3] + c[4] == 1]
    for cb in comp:
        print(cb)

It seems I am not getting all possible combinations. For instance, the first line of output would be

(0.1, 0.1, 0.1, 0.1, 0.6)

but does not include any of the following

(0.6, 0.1, 0.1, 0.1, 0.1)
(0.1, 0.6, 0.1, 0.1, 0.1)
(0.1, 0.1, 0.6, 0.1, 0.1)
(0.1, 0.1, 0.1, 0.6, 0.1)

and so on. I also tried different approaches with

itertools.combinations_with_replacement
itertools.permutations

Do you want all possible permutations instead, since you consider `(0.1, 0.1, 0.1, 0.1, 0.6)` and `(0.6, 0.1, 0.1, 0.1, 0.1)` different? — blhsing, Jan 15 '19 at 19:12
I believe you need permutation once you found the numbers whose sum is 1.`list(permutations((0.6, 0.1, 0.1, 0.1, 0.1)))` — mad_, Jan 15 '19 at 19:14
Permutations should be a subset of the products, so that's not the issue. I think it's the floating point issue. — cadolphs, Jan 15 '19 at 19:27

score 5 · Accepted Answer · edited Jan 15 '19 at 19:37

5

The itertools.product function does output what you want, the problem is in checking the equality of floating numbers, for that you can use math.isclose:

from itertools import product
import math
comb = [c for c in product(number, repeat=5) if math.isclose(sum(c), 1.0)]

edited Jan 15 '19 at 19:37

Ajax1234

69,937
8
61
102

answered Jan 15 '19 at 19:17

Dani Mesejo

61,499
6
49
76

1

Yes, I was thinking product function was giving most of the right answer but did not think about the floating issue. Many thanks – asmsr2 Jan 15 '19 at 20:04

Marcus · Answer 2 · 2019-01-15T19:21:50.667

2

This looks like an interesting case of floating point arithmetic errors resulting in the sum being incorrect. More information can be found in the python documentation.

Here's an example of what's going on:

>>> 0.1 + 0.6 + 0.1 + 0.1 + 0.1 == 1
False

A solution would be to check if the sum is within some margin of error of 1:

comb = [c for c in itertools.product(number, repeat=5) if abs(sum(c)  - 1) <= .01]

Alternatively, you can round the sum and compare to fix the issue as well, like so:

comb = [c for c in itertools.product(number, repeat=5) if round(sum(c), 2) == 1]

edited Jan 15 '19 at 19:21

answered Jan 15 '19 at 19:16

Marcus

3,216
2
22
22

@mad-physicist there is a typo in the code comp should be comb – asmsr2 Jan 15 '19 at 20:52

Mad Physicist · Answer 3 · 2019-01-15T19:50:22.557

As the other answers correctly point out, the issue is with floating point comparisons. Tenths don't have finite binary representations unless there are five of them.

Since you are interested in a very particular set of numbers, you could map them to integers instead of using round, isclose or abs comparison. That way you could make the comparison exact, then map the results back to the numbers you want.

In this case, you can multiply everything by 10 to get integers. For more complicated cases, you might need other factors, entirely different transformation function, or even possibly a lookup table.

number = range(1, 10)
comb = (tuple(x / 10 for x in c) for c in itertools.product(number, repeat=5) if sum(c) == 10)
for cb in comp:
    print(cb)

Couple of other minor improvements:

Use sum to add up the elements together instead of writing it out manually. It will make it much easier to add more elements to the sum.
Keep comb as a generator instead of turning it into a memory-hogging list unless you need to access it multiple times.

How to get all possible combinations with constraints?

3 Answers3