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'}