Solve every possible combination of #s in a list that add up to a predetermined # w/out repeating # in list more than how many times they appear?

by

I’m trying to figure out how to loop through a list and solve every possible combination of numbers that add up to a predetermined value without repeating any numbers in the combination more than how ever many times they appear on the list.

Here’s the code I tried:

import itertools

magicnumber = float(input("Enter desired quantity : "))

lst = [2.7, 9.9, 5.4, 9.0, 5.4, 8.1, 6.3, 4.5, 5.4]

for L in range(0, len(lst)+1):
    for subset in itertools.combinations(lst, L):
        b = sum(float(i) for i in subset)
            
        if b == magicnumber:
            print(subset)

I tried solving all combinations that add up to 18.9 in the list, but can’t figure out how to not have the numbers repeat when adding more than they appear on the list.

I want it to return all combinations like below that add up to 18.9 using only the numbers in the list once, and more than once only how ever many times they repeat.

The result I want to get is:

(9.9, 9.0)
(5.4, 5.4, 8.1)
(2.7, 6.3, 4.5, 5.4)

What I’m currently getting:

(9.9, 9.0)
(5.4, 9.0, 4.5)
(5.4, 5.4, 8.1)
(5.4, 8.1, 5.4)
(9.0, 5.4, 4.5)
(9.0, 4.5, 5.4)
(5.4, 8.1, 5.4)
(8.1, 6.3, 4.5)
(2.7, 6.3, 4.5, 5.4)

  • 1

    Sorting might be of use here.

    – 

  • Why doesn’t your desired result include (5.4, 9.0, 4.5)?

    – 

  • 2

    You CAN’T use equality here. With two exceptions, none of the numbers in your list (including 18.9) can be expressed in binary. They will all be approximations, and round-off errors means they would add up. You need to use a “close to” function that checks, for example, that abs(a-b) < 0.0001 or something similar.

    – 

  • 1

    So, once you use a number in a subset, you can’t use it again? Is the goal to use as many of the numbers as possible? That’s a much more difficult problem, because it requires backtracking. You will have to remove each set from the master set and continue processing.

    – 




  • 1

    Once you deal with the floating-point issue (scaling up everything by 10 would work in this particular case), this is easily solved by recursion. The number of combinations from a list that sum to a given total (let’s call that NC(L, T) is the sum of the number of combinations from the rest of the list, ignoring the first one (that’s just NC(L[1:], T)) plus the number of combinations from the rest of the list, including the first one (which is NC(L[1:], T-L[0])).

    – 

I would get all possible combination as you have stated in your question and then just check if the combination is valid:

import itertools
from collections import Counter


def is_combination_valid(subset, cnt):
    cnt_subset = Counter(subset)

    if any(cnt[c] < cnt_subset.get(c, float("inf")) for c in subset):
        return False

    for v in subset:
        cnt[v] -= 1

    return True


magicnumber = 18.9
lst = [2.7, 9.9, 5.4, 9.0, 5.4, 8.1, 6.3, 4.5, 5.4]

cnt = Counter(lst)

for L in range(0, len(lst) + 1):
    for subset in itertools.combinations(lst, L):
        b = sum(subset)
        if b == magicnumber and is_combination_valid(subset, cnt):
            print(subset)

Prints:

(9.9, 9.0)
(5.4, 5.4, 8.1)
(2.7, 6.3, 4.5, 5.4)

With:

magicnumber = 18.9
lst = [8.1, 9.9, 5.4, 9.0, 5.4, 8.1, 6.3, 4.5, 5.4]

It prints:

(9.9, 9.0)
(8.1, 5.4, 5.4)
(8.1, 6.3, 4.5)

Leave a Comment