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

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

4 голосов
/ 10 сентября 2010

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

   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 ]

2 голосов
/ 10 сентября 2010

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

#!/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')]
1 голос
/ 10 сентября 2010

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

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

item_set[category].append(item)

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

...