sharing/swapping items between lists

[samwyse]

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.