# sharing/swapping items between lists

Wed Apr 15 23:08:01 CEST 2009

```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
>> 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: