sharing/swapping items between lists

[MRAB]

samwyse wrote:
> On Apr 15, 8:13 am, Aaron Brady <castiro... at gmail.com> wrote:
>> On Apr 15, 6:57 am, samwyse <samw... at gmail.com> wrote:
>>
>>> Here's my idea:  generate all possible pairs:
>>>>>> import itertools
>>>>>> players = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
>>>>>> all_pairs = list(itertools.combinations(players,2))
>>> partition the list:
>>>>>> def choose_nonoverlapping(pairs):
>>>         chosen, leftover, used = list(), list(), list()
>>>         for p in pairs:
>>>                 a, b = p
>>>                 if a in used or b in used:
>>>                         leftover.append(p)
>>>                 else:
>>>                         chosen.append(p)
>>>                         used.append(a)
>>>                         used.append(b)
>>>         return chosen, leftover
>>>>>> court_count = 10
>>>>>> week_count = 10
>>>>>> pairs = all_pairs
>>>>>> for week in xrange(week_count):
>>>         print 'week', week+1
>>>         this_week, pairs = choose_nonoverlapping(pairs)
>>>         print ', '.join(map(lambda t: ' vs '.join(t), this_week
>>> [:court_count]))
>>>         pairs[0:0] = this_week[court_count:]
>> snip
>>
>> Your idea arrives at a sub-optimal solution on players= 'abcdef',
>> court_count= 3.
>>
>> Correct, by hand (5 weeks):
>>
>> ab cd ef
>> ac be df
>> ad ce bf
>> ae bd cf
>> af bc de
>>
>> Program (7 weeks):
>>
> [snip]
>> However, you do correctly arrive at all the combinations, in better
>> than the naive 'one pair per week' solution.  Further, you produced
>> the correct solution for players= 'abcdef', for court_count= 1 and
>> court_count= 2, which I also tested.  Damage report?
> 
> It does work better when there are a limited number of courts, but
> since that was in the original description, I didn't worry too much.
> 
> One could product several random shuffles of the list of combinations
> and see which produced the shortest list of results.  That would add
> indeterminancy without guaranteeing an optimal result.  But I think
> that other people have algorithms for that case, so I'm not too
> worried.
> 
> I've tried generalizing to competitions  with more than two player
> (e.g. the Pinewood Derby, where up four cars are in each heat), but
> the algorithm falls apart, mostly due to the way
> itertools.combinations returns its results.
> 
Here's the basics of my algorithm, for what it's worth. It just returns
the pairs:

def get_pair(player_queue, done_pair):
     for first in player_queue:
         for second in player_queue:
             pair = first, second
             if first != second and pair not in done_pair:
                 return pair
     return None

def round_robin(players):
     player_queue = players[:]
     done_pair = set()
     while True:
         pair = get_pair(player_queue, done_pair)
         if pair is None:
             player_queue = players[:]
             break
         else:
             done_pair.add(pair)
             done_pair.add((pair[1], pair[0]))
             player_queue = [p for p in player_queue if p not in pair] + 
list(pair)
             yield pair

for pair in round_robin('abcdef'):
     print pair