Combinations meeting certain numeric criteria

Question

I need to generate combinations and limit the output to certain combos which meet a numeric criteria associated with the combo. Here are the codes:

import itertools

mylist = [('Beef', 1), ('Pepper', -1),('Onion', 6), ('Green', -1), ('Chicken', 4)]

lst = [item[0] for item in mylist]

combo = []
for i in range(1, 5):
    for tpl in itertools.combinations(lst, i):
        combo.append(tpl)
print(combo)

The code currently generates all possible combinations. I need to limit the result to only those combos where the value is certain numeric value. For example, if my value is 9, then the combo should be generated using "Onion", "Green", and "Chicken", or "Onion", "Chicken", and "Pepper". Because their numeric value adds up to 9 (6+4-1=9). In this case, beef is excluded from the combo generation. How can I do that?

This is "subset sum" in disguise, an [optimal solution](https://stackoverflow.com/a/70736556/14277722) has O(n^2) complexity. `1 + -1 + 6 + 4 + -1` (all items) should include "beef". — Michael Szczesny, Jul 21 '22 at 13:30

Tomerikoo · Answer 1 · 2022-07-21T13:30:09.770

Instead of separating the strings to a different list, use the tuples and add a condition on the values and only add the strings that meet the criteria:

import itertools

goal = 9
mylist = [('Beef', 1), ('Pepper', -1),('Onion', 6), ('Green', -1), ('Chicken', 4)]

combo = []
for i in range(1, 5):
    for tpl in itertools.combinations(mylist, i):
        if sum(item[1] for item in tpl) == goal:
            combo.append(tuple(item[0] for item in tpl))
print(combo)

For the case above of goal = 9, this will give:

[('Pepper', 'Onion', 'Chicken'), ('Onion', 'Green', 'Chicken')]

A more "pythonic" way to separate the list of tuples to two lists, is by transposing the list:

    for tpl in itertools.combinations(mylist, i):
        names, values = zip(*tpl)
        if sum(values) == goal:
            combo.append(names)

Combinations meeting certain numeric criteria

1 Answers1