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