CODEWITHSUNDEEP
pythonlistuniquepermutation
mcnollster
mcnollster

Reputation: 537

python - check if permutation exists/combination is unique

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.

Upvotes: 3

Views: 1371

Answers (3)

thefourtheye
thefourtheye

Reputation: 239503

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)

Upvotes: 3

Aaron Hall
Aaron Hall

Reputation: 395155

Eliminate redundant sets after creation:

You can make a set of frozensets, which will eliminate redundant sets:

>>> tup_1 = ('apple', 'banana', 'tomato', 'cucumber', 'water', 'soda', 10)
>>> tup_2 = ('banana', 'apple', 'tomato', 'cucumber', 'water', 'soda', 10)
>>> fs_1 = frozenset(tup_1)
>>> fs_2 = frozenset(tup_2)
>>> set([fs_1, fs_2])
set([frozenset(['tomato', 'apple', 10, 'water', 'cucumber', 'soda', 'banana'])])

You need a frozenset for each item because elements of a set must be hashable. Keep in mind you lose ordering with this method.

Ensure no redundancy prior:

Also, itertools.combinations will ensure that you don't get redundant items:

import itertools
fruits = [('apple', 1), ('banana', 2), ('orange', 3)]
veggies = [('tomato', 1), ('cucumber', 2), ('onion', 3)]
drinks = [('water', 1), ('juice', 2), ('soda', 3)]
combs=(itertools.combinations(fruits, 2), 
       itertools.combinations(veggies, 2), 
       itertools.combinations(drinks, 2))
multi_combs = [list(itertools.chain.from_iterable(i)) 
                    for i in itertools.product(*combs)]

print(len(multi_combs))

prints

27

And then you can filter:

filtered_combs = [i for i in multi_combs 
                      if 12 <= sum(p for _, p in  i) <= 14]

and 

len(filtered_combs)

is 

16

Results:

And to pretty print the items, with the sums:

printable = [list(itertools.chain((j for j, _ in i), 
                                  [sum(p for _, p in  i),])) 
                                      for i in filtered_combs]

pprint.pprint(printable)

prints

[['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]]

Upvotes: 1

DSM
DSM

Reputation: 353189

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]

Upvotes: 1

Related Questions