Create limited permutations of a list of items by category

Question

I am trying to create a series of limited permutations of a list of items. Each element has a category, and I need to find combinations of elements so that each combination does not have several elements from the same category. To illustrate a few sample data here:

Name | Category ==========|========== 1. Orange | fruit 2. Apple | fruit 3. GI-Joe | toy 4. VCR | electronics 5. Racquet | sporting goods 

Combinations will be limited to three, I do not need every combination of each length. Thus, the set of combinations for the above list can be:

 (Orange, GI-Joe, VCR) (Orange, GI-Joe, Racquet) (Orange, VCR, Racquet) (Apple, GI-Joe, VCR) (Apple, GI-Joe, Racquet) ... and so on. 

I do this quite often, on different lists. Lists will not contain more than 40 items, but it is clear that they can create thousands of combinations (although each list will probably have about 10 unique categories, which somewhat limits them)

I came up with some pseudo python for how I will implement it recursively. It was too long since I took combinatorics, but from what I remember, it is, in fact, a subset of the combination of the set, something like C (list length, desired size). Probably some library modules that can make this cleaner (or at least more efficient)

I was wondering if it is possible that there is a better approach than what I have (maybe one that uses itertools.combinations ):

 # For the sake of this problem, let assume the items are hashable so they # can be added to a set. def combinate(items, size=3): assert size >=2, "You jerk, don't try it." def _combinate(index, candidate): if len(candidate) == size: results.add(candidate) return candidate_cats = set(x.category for x in candidate) for i in range(index, len(items)): item = items[i] if item.category not in candidate_cats: _combinate(i, candidate + (item, )) results = set() for i, item in enumerate(items[:(1-size)]): _combinate(i, (item, )) return results 

Answer 1

Naive approach:

 #!/usr/bin/env python import itertools items = { 'fruits' : ('Orange', 'Apple'), 'toys' : ('GI-Joe', ), 'electronics' : ('VCR', ), 'sporting_goods' : ('Racquet', ) } def combinate(items, size=3): if size > len(items): raise Exception("Lower the `size` or add more products, dude!") for cats in itertools.combinations(items.keys(), size): cat_items = [[products for products in items[cat]] for cat in cats] for x in itertools.product(*cat_items): yield zip(cats, x) if __name__ == '__main__': for x in combinate(items): print x 

Will yield:

 # ==> # # [('electronics', 'VCR'), ('toys', 'GI-Joe'), ('sporting_goods', 'Racquet')] # [('electronics', 'VCR'), ('toys', 'GI-Joe'), ('fruits', 'Orange')] # [('electronics', 'VCR'), ('toys', 'GI-Joe'), ('fruits', 'Apple')] # [('electronics', 'VCR'), ('sporting_goods', 'Racquet'), ('fruits', 'Orange')] # [('electronics', 'VCR'), ('sporting_goods', 'Racquet'), ('fruits', 'Apple')] # [('toys', 'GI-Joe'), ('sporting_goods', 'Racquet'), ('fruits', 'Orange')] # [('toys', 'GI-Joe'), ('sporting_goods', 'Racquet'), ('fruits', 'Apple')] 

Answer 2

What you are trying to create are Cartesian product elements taken from the category set.

Dividing into multiple sets is relatively simple:

 item_set[category].append(item) 

With the proper instance (for example) collections.defaultdict for item_set[category] and then itertools.product will give you the desired result.