Создание ограниченных перестановок списка предметов по категориям

Question

Я пытаюсь создать ряд ограниченных перестановок списка элементов. Каждый элемент имеет категорию, и мне нужно найти комбинации элементов, чтобы каждая комбинация не имела нескольких элементов из той же категории. Чтобы проиллюстрировать это, вот некоторые примерные данные:

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

комбинация будет ограничен длиной три, мне не нужен каждая комбинация каждой длины. Таким образом, набор комбинаций для вышеуказанного списка может быть:

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

Я делаю это довольно часто в разных списках. Списки не будут содержать более 40 наименований, но понятно, что это может создать тысячи комбинаций (хотя в каждом списке будет, по-видимому, около 10 уникальных категорий, ограничивающих его)

Я придумал несколько псевдо -python о том, как я буду реализовывать его рекурсивно. Это было слишком долго, так как я взял комбинаторика, но из того, что я помню, это, по сути, подмножество комбинаций набора, что-то вроде C (длина списка, желаемый размер). Там, скорее всего, некоторые библиотечные модули, которые могут сделать этот очиститель (или, по крайней мере, более производительный)

мне было интересно, если возможно, был лучший подход, чем то, что у меня есть (возможно, один, который использует itertools.combinations каким-то образом):

# For the sake of this problem, let's 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

Наивный подход:

#!/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 

даст:

# ==> 
# 
# [('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

То, что вы ищете, является декартово product элементов, взятых из набора category.

Разделение на несколько наборов относительно легко:

item_set[category].append(item) 

При надлежащем конкретизации (например) collections.defaultdict для item_set[category], а затем itertools.product даст вам желаемый результат.