按类别创建受限排列列表

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

你想要生成的是从category这个集合中取出的元素的笛卡尔积。

把这些元素分成多个集合其实比较简单：

item_set[category].append(item)

只要正确地创建实例，比如使用collections.defaultdict来处理item_set[category]，然后用itertools.product就能得到你想要的结果。

Answer 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')]