I have a list of tuples (item, value) and I want to get all its possible combinations up to a max total value except the "subcombinations" of those already found. Suppose I have list:
items = [("a", 1), ("b", 3), ("b", 3), ("c", 10), ("d", 15)]
combinations = [combo for i in range(len(items), 0, -1) for combo in list(itertools.combinations(items, i)) if sum([item[1] for item in combo]) < 16]
The result is:
[(('a', 1), ('b', 3), ('b', 3)), (('a', 1), ('b', 3), ('c', 10)), (('a', 1), ('b', 3), ('c', 10)), (('a', 1), ('b', 3)), (('a', 1), ('b', 3)), (('a', 1), ('c', 10)), (('a', 1), ('d', 15)), (('b', 3), ('b', 3)), (('b', 3), ('c', 10)), (('b', 3), ('c', 10)), (('a', 1),), (('b', 3),), (('b', 3),), (('c', 10),), (('d', 15),)]
but I want to get:
[(('a', 1), ('b', 3), ('b', 3)), (('a', 1), ('b', 3), ('c', 10)), (('d', 15))]
Is it possible to eliminate the "subcombinations" except doing it by many long ifs (the actual list is much larger)?
Ok, this should work.
from itertools import combinations
items = [("a", 1), ("b", 3), ("b", 3), ("c", 10), ("d", 15)]
res = []
for l in range(len(items), 0, -1):
cb = combinations(items, l)
cbl = [i for i in cb if sum([j[1] for j in i]) < 16]
for cc in cbl:
if not any([set(cc).issubset(el) for el in res]):
res.append(cc)
print(res)
This prints:
[(('a', 1), ('b', 3), ('b', 3)), (('a', 1), ('b', 3), ('c', 10)), (('d', 15),)]
Please note that this code may be slow if you have a lot of items, because it iterates many times to check if a given combination is not a subset of any already accepted combination. Maybe there are more efficient solutions.