0

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)?

Kazek Ciaś
  • 5
  • 1
  • 5
  • Not sure I understand what you're trying to do, but if you generate just the set of longest possible combinations, all shorter combinations will be a subset of at least one of them. – glibdud Jan 10 '19 at 18:42
  • 1
    Your code is not working. What is `t`? – Sheldore Jan 10 '19 at 18:49
  • Why don't you want `(('a', 1),)` or `(('b', 3),)` or `(('c', 10),)` as results? – Calvin Godfrey Jan 10 '19 at 19:06
  • @glibdud yeah, the example is a bit bad, but I didn't want the result to be too long, I'll change it when I think of a better one. The problem is the max sum: often a shorter combination contains an item that none of the longer ones do. – Kazek Ciaś Jan 10 '19 at 19:11
  • To me is not clear if you want combinations of 3 elements which satisfiy the `sum(...) < 16` criterion or any length is fine as long the sum is <16. – Valentino Jan 10 '19 at 19:20
  • @Valentino yeah, as I said in the previous comment, the example is bad, and I'll try my best to think of a better one. I want combinations of any length that aren't subsets of any others. – Kazek Ciaś Jan 10 '19 at 19:27
  • 1
    When I try to run the code in your question I get `NameError: name 't' is not defined`. Please [edit] your question and put in something runnable. – martineau Jan 10 '19 at 19:39
  • @martineau Yeah sorry, you're right. Now it should be okay. – Kazek Ciaś Jan 10 '19 at 19:48

1 Answers1

0

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.

Valentino
  • 7,291
  • 6
  • 18
  • 34