On Apr 15, 6:57 am, samwyse <samw...@gmail.com> wrote:
> On Apr 14, 7:01 pm, Aaron Brady <castiro...@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?
--
http://mail.python.org/mailman/listinfo/python-list
