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

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

   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 уникальных категорий в каждом списке, несколько ограничивая его)

Я придумал какой-то псевдопифон для того, как я бы реализовал его рекурсивно. Прошло слишком много времени с тех пор, как я брал комбинаторику, но из того, что я помню, это по существу подмножество комбинаций множества, что-то вроде 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
2 4
python combinatorics

2 ответа:

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

#!/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')]
2

То, что вы стремитесь сгенерировать, - это декартово произведение элементов, взятых из множества category.

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

item_set[category].append(item)

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

1