need to get highest combination

Question

I have a list of lists and I need to find the highest combination of values given some constraints:

for example let's say I have:

lst1 = [['a', 1, 100], ['b', 2, 200], ['c', 1.5, 300]]
lst2 = [['d', 1, 100], ['e', 2, 200], ['f', 1.5, 300]]
lst3 = [['g', 5, 100], ['h', 9, 200], ['i', 11, 500]]

If I wanted to get the combination of 1 selection from each list with the highest sum of the 2nd values and the sum of the third values being under 401.

so a possible combination would be ['a', 'd', 'g'] or ['b', 'd', 'h'].

Is there a library optimized for this or would I need to just do something like:

from itertools import product
combinations = list(product(lst1, lst2, lst3))
outcomes = []
for index, combination in enumerate(combinations):
    first_total = 0
    second_total = 0
    for member in combination:
        first_total += member[1]
        second_total += member[2]
    if second_total <= 400:
        outcomes.append((index, first_total,))

What would the expected output be given the input you have in the question? (I couldn't follow your explanation.) — user94559
– user94559, Commented Jul 15, 2016 at 2:33
Maybe the answer here would be [['a', ...], ['d', ...], ['g', ...]]? (One item from each of the three lists, and the sum of the third element of each item has to sum to less than 400, making that the only legal combination?) — user94559
– user94559, Commented Jul 15, 2016 at 2:38
just the combination with the highest sum of the 2nd elements and the 3rd elements < 400 — Rob
– Rob, Commented Jul 15, 2016 at 2:39
ok i see the miscommunication, i would want a combination of one element from each of lst1, lst2 and lst3 so there would be 9 possible combinations — Rob
– Rob, Commented Jul 15, 2016 at 2:39

user94559 · Accepted Answer · 2016-07-15 02:49:46Z

I can think of more efficient mechanisms than what you're doing (e.g. pruning when the total already exceeds 400), but I can't think of ways to make the code much clearer. Here's a short working version in case that helps:

from itertools import product

def find_best(lists):
    return max(
        (combination for combination in product(*lists) if
            sum(x[2] for x in combination) < 400
        ), key=lambda combination:
            sum(x[1] for x in combination))

lists = [
    [['a', 1, 100], ['b', 2, 200], ['c', 1.5, 300]],
    [['d', 1, 100], ['e', 2, 200], ['f', 1.5, 300]],
    [['g', 5, 100], ['h', 9, 200], ['i', 11, 500]],
]

print(find_best(lists))

# Output:
# (['a', 1, 100], ['d', 1, 100], ['g', 5, 100])

Collectives™ on Stack Overflow

need to get highest combination

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related