python - check if permutation exists/combination is unique

Question

I have the following code which creates combinations of fruits, veggies, and drinks that falls within a certain price range:

fruits = [('apple', 1), ('banana', 2), ('orange', 3)]
veggies = [('tomato', 1), ('cucumber', 2), ('onion', 3)]
drinks = [('water', 1), ('juice', 2), ('soda', 3)]

for fruit1 in fruits:
    for fruit2 in fruits:
        for veggie1 in veggies:
            for veggie2 in veggies:
                for drink1 in drinks:
                    for drink2 in drinks:
                        if 12 <= fruit1[1]+fruit2[1]+veggie1[1]+veggie2[1]+drink1[1]+drink2[1] <= 14: 
                            if fruit1 != fruit2: 
                                if veggie1 != veggie2: 
                                    if drink1 != drink2:
                                        combos.append((fruit1[0], fruit2[0], veggie1[0], veggie2[0], drink1[0], drink2[0], fruit1[1]+fruit2[1]+veggie1[1]+veggie2[1]+drink1[1]+drink2[1])) 

It checks to make sure it doesn't pick the same fruit/veggie/drink twice but I need to make sure the combinations are unique.

For example, if I end up with

('apple', 'banana', 'tomato', 'cucumber', 'water', 'soda', 10) 

I don't also want

('banana', 'apple', 'tomato', 'cucumber', 'water', 'soda', 10)

and so on. This is giving me more trouble than it should so any help is appreciated.

Answer 1

You can process the data like this

prices = {k:v for items in [fruits, veggies, drinks] for k, v in items}
fru,veg,dri=[i[0] for i in fruits],[i[0] for i in veggies],[i[0] for i in drinks]

from itertools import combinations, product, chain
for items in product(*(combinations(i, r = 2) for i in (fru, veg, dri))):
    total = sum(prices[i] for item in items for i in item)
    if 12 <= total <= 14:
        print tuple(chain.from_iterable(items)) + (total,)

Output

('apple', 'banana', 'tomato', 'onion', 'juice', 'soda', 12)
('apple', 'banana', 'cucumber', 'onion', 'water', 'soda', 12)
('apple', 'banana', 'cucumber', 'onion', 'juice', 'soda', 13)
('apple', 'orange', 'tomato', 'cucumber', 'juice', 'soda', 12)
('apple', 'orange', 'tomato', 'onion', 'water', 'soda', 12)
('apple', 'orange', 'tomato', 'onion', 'juice', 'soda', 13)
('apple', 'orange', 'cucumber', 'onion', 'water', 'juice', 12)
('apple', 'orange', 'cucumber', 'onion', 'water', 'soda', 13)
('apple', 'orange', 'cucumber', 'onion', 'juice', 'soda', 14)
('banana', 'orange', 'tomato', 'cucumber', 'water', 'soda', 12)
('banana', 'orange', 'tomato', 'cucumber', 'juice', 'soda', 13)
('banana', 'orange', 'tomato', 'onion', 'water', 'juice', 12)
('banana', 'orange', 'tomato', 'onion', 'water', 'soda', 13)
('banana', 'orange', 'tomato', 'onion', 'juice', 'soda', 14)
('banana', 'orange', 'cucumber', 'onion', 'water', 'juice', 13)
('banana', 'orange', 'cucumber', 'onion', 'water', 'soda', 14)

If you want to pick only one element in drinks then you can change the combinations part like this

d = {0: 2, 1: 2, 2: 1}
for items in product(*(combinations(j, r=d.get(i)) for i, j in enumerate((fru,veg,dri)))):

With that change, the output becomes

('apple', 'orange', 'cucumber', 'onion', 'soda', 12)
('banana', 'orange', 'tomato', 'onion', 'soda', 12)
('banana', 'orange', 'cucumber', 'onion', 'juice', 12)
('banana', 'orange', 'cucumber', 'onion', 'soda', 13)

Answer 2

This isn't that efficient a way to do it, because once you've spent more than 14 units you don't need to keep searching. But you can use itertools to simplify -- or at least flatten -- the brute force approach:

from itertools import combinations, product, chain

fruits = [('apple', 1), ('banana', 2), ('orange', 3)]
veggies = [('tomato', 1), ('cucumber', 2), ('onion', 3)]
drinks = [('water', 1), ('juice', 2), ('soda', 3)]

options = fruits, veggies, drinks
possibles = product(*(combinations(opt, 2) for opt in options))
purchases = (list(chain.from_iterable(p)) for p in possibles)
within_range = [p for p in purchases if 12 <= sum(price for _, price in p) <= 14]

produces

>>> within_range[0]
[('apple', 1), ('banana', 2), ('tomato', 1), ('onion', 3), ('juice', 2), ('soda', 3)]
>>> within_range[-1]
[('banana', 2), ('orange', 3), ('cucumber', 2), ('onion', 3), ('water', 1), ('soda', 3)]
>>> [sum(p for _,p in w) for w in within_range]
[12, 12, 13, 12, 12, 13, 12, 13, 14, 12, 13, 12, 13, 14, 13, 14]