按類別創建項目列表的限制排列

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，我將如何遞歸地實現它。自從我使用combinatorics的時間太長了，但從我記得這基本上是組合的一個子集，就像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

幼稚的做法：

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

Answer 2

您試圖生成的是從category集合中取得的元素的笛卡爾product。

劃分成多組相對容易：

item_set[category].append(item) 

通過適當實例（例如）爲collections.defaultdictitem_set[category]然後itertools.product會給你所需的輸出。