代码之家 › 专栏 › 技术社区 › Crast

按类别创建项目列表的限制排列

combinatorics set python

Crast · 技术社区 · 14 年前

我试图创建一个项目列表的限制排列的数量。每个项目都有一个类别,我需要找到项目的组合,这样每个组合就不会有来自同一类别的多个项目。下面是一些示例数据:

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

组合长度限制为3,我不需要每种长度的组合。因此,上述列表的一组组合可以是:

(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

2 回复 | 直到 14 年前

miku 14 年前

天真的方法:

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

msw 14 年前

你想要产生的是笛卡尔坐标 product 从一组 category .

划分为多个集合相对容易:

item_set[category].append(item)

适当的实例化(例如) collections.defaultdict 对于 item_set[category] itertools.product 会给你想要的输出。