sharing/swapping items between lists

Aaron Brady castironpi at gmail.com
Wed Apr 15 15:13:44 CEST 2009


On Apr 15, 6:57 am, samwyse <samw... at gmail.com> wrote:
> On Apr 14, 7:01 pm, Aaron Brady <castiro... at gmail.com> wrote:
>
> > Here is an idea.  Create a list of all possible pairs, using
> > itertools.combinations.  You'll notice everyone gets equal play time
> > and equal time against each other on a pair-by-pair basis.  Then, call
> > random.shuffle until one player isn't playing on two courts in one
> > day.
>
> > It has the disadvantage that you might end up with player A playing
> > lots early on and rarely at the end, and B rarely early on and lots at
> > the end.  Perhaps you could generate a few to several correct
> > solutions, then choose the most evenly distributed.  Does this make
> > sense?
>
> 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):

week 1
a vs b, c vs d, e vs f
week 2
a vs c, b vs d
week 3
a vs d, b vs c
week 4
a vs e, b vs f
week 5
a vs f, b vs e
week 6
c vs e, d vs f
week 7
c vs f, d vs e

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?



More information about the Python-list mailing list