我正在尝试创建一系列项目的限制排列。每个项目都有一个类别,我需要找到项目的组合,以便每个组合不包含来自同一类别的多个项目。下面是一些示例数据:
Name | Category
==========|==========
1. Orange | fruit
2. Apple | fruit
3. GI-Joe | toy
4. VCR | electronics
5. Racquet | sporting goods
组合的长度限制在3,我不需要每个长度的组合。因此,上述列表的一组组合可以是:
^{pr2}$我经常这样做,在各种各样的清单上。列表的长度永远不会超过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
天真的方法:
将产生:
^{pr2}$您要生成的是从
category
集合中提取的元素的笛卡尔product。在划分为多个集合相对容易:
通过正确的实例化(例如,collections.defaultdictfor
item_set[category]
,然后itertools.product
将为您提供所需的输出。在相关问题 更多 >
编程相关推荐