pythonic way to maximize the number of items that fit in a list of available spots
Question: Here is the problem. Each item has an index value, and the slots it could fit
into.

    
    
    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']),
    )
    

What is the largest list of slots with these items fit into. No slot can be
you more than once.

My solution seems hard to follow, and very non-pythonic [and fails on the last
item]. I didn't want to ask a "what's better" question before solving the prob
myself [so now hear I am, beggar's hat in hand]. Here's my code:

    
    
    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: Simply trying every possibility has a certain brutal elegance:

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

Admittedly it doesn't scale very well, though.

[edit]

.. and, as noted in the comments, it only finds a solution if there's a
filling solution. A slightly more efficient (but still brute-force) solution
works even if there isn't:

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

