pythonic方式最大限度地提供適合可用點列表的項目數量

Question

以下是問題所在。每個項目都有一個索引值，以及它可以放入的插槽。

items = (#(index, [list of possible slots]) 
    (1, ['U', '3']), 
    (2, ['U', 'L', 'O']), 
    (3, ['U', '1', 'C']), 
    (4, ['U', '3', 'C', '1']), 
    (5, ['U', '3', 'C']), 
    (6, ['U', '1', 'L']), 
) 

什麼是適合這些項目的插槽的最大列表。沒有插槽可以超過一次。

我的解決方案似乎很難遵循，而且非pythonic [並在最後一項失敗]。在我自己解決問題之前，我不想問一個「什麼更好」的問題[所以現在聽到我是，乞丐的帽子在手]。這裏是我的代碼：

def find_available_spot(item, spot_list): 
    spots_taken = [spot for (i,spot) in spot_list] 
    i, l = item 
    for spot in l: 
     if spot not in spots_taken: return (i, spot) 
    return None 

def make_room(item, spot_list, items, tried=[]): 
    ORDER = ['U','C','M','O','1','3','2','L'] 
    i, l = item 
    p_list = sorted(l, key=ORDER.index) 
    spots_taken = [spot for (i, spot) in spot_list] 

    for p in p_list: 
     tried.append(p) 
     spot_found = find_available_spot((i,[p]),spot_list) 
     if spot_found: return spot_found 
     else: 
      spot_item = items[spots_taken.index(p)] 
      i, l = spot_item 
      for s in tried: 
       if s in l: l.remove(s) 
      if len(l) == 0: return None 

      spot_found = find_available_spot((i,l),spot_list) 
      if spot_found: return spot_found 

      spot_found = make_room((i,l), spot_list, items, tried) 
      if spot_found: return spot_found 
      return None 

items = (#(index, [list of possible slots]) 
    (1, ['U', '3']), 
    (2, ['U', 'L', 'O']), 
    (3, ['U', '1', 'C']), 
    (4, ['U', '3', 'C', '1']), 
    (5, ['U', '3', 'C']), 
    (6, ['U', '1', 'L']), 
) 

spot_list = [] 
spots_taken = [] 
for item in items: 
    spot_found = find_available_spot(item, spot_list) 
    if spot_found: 
     spot_list.append(spot_found) 
    else: 
     spot_found = make_room(item,spot_list,items) 
     if spot_found: spot_list.append(spot_found) 

Answer 1

只是想一切可能具有一定的殘酷的優雅：

>>> items = (
...  (1, ['U', '3']), 
...  (2, ['U', 'L', 'O']), 
...  (3, ['U', '1', 'C']), 
...  (4, ['U', '3', 'C', '1']), 
...  (5, ['U', '3', 'C']), 
...  (6, ['U', '1', 'L']), 
...) 
>>> import itertools 
>>> locs = zip(*items)[1] 
>>> max((len(p), p) for p in itertools.product(*locs) if len(p) == len(set(p))) 
(6, ('U', 'O', 'C', '1', '3', 'L')) 

誠然它不規模非常好，雖然。

[編輯]

..和，如在評論中指出，只找到一個解決方案，如果有一個填充液。即使沒有，效率稍高的（但仍然蠻力）解決方案工作：

def find_biggest(items): 
    for w in reversed(range(len(items)+1)): 
     for c in itertools.combinations(items, w): 
      indices, slots = zip(*c) 
      for p in itertools.product(*slots): 
       if len(set(p)) == len(p): 
        return dict(zip(indices, p)) 

>>> items = ((1, ['U', '3']), (2, ['U', 'L', 'O']), (3, ['U', '1', 'C']), (4, ['U', '3', 'C', '1']), (5, ['U', '3', 'C']), (6, ['U', '1']), (7, ['U', '1', 'L']),) 
>>> find_biggest(items) 
{1: 'U', 2: 'O', 3: '1', 4: '3', 5: 'C', 7: 'L'}