John Yeung <gallium.arsen...@gmail.com> writes:
> On May 5, 11:37 pm, Ross <ross.j...@gmail.com> wrote:
>
>> On May 5, 10:33 am, MRAB <goo...@mrabarnett.plus.com> wrote:
>>
>> > Here's my approach (incomplete):
>>
>> FYI... I was testing your code further and discovered a strange
>> outcome... when there are 16 people for 7 courts, every 7th
>> round your code produces 4 byes instead of the correct 2 byes.
>
> Well, MRAB did say his was incomplete, and it's significantly shorter
> and cleaner than mine.
>
> Mine has even weirder-looking behavior at 16 players on 7 courts, but
> I think it's because mine tries harder to keep things balanced. After
> a few rounds, the inequalities start to build up, and my routine picks
> some people more often to "catch up", but it doesn't prevent the same
> person from being scheduled for multiple matches the same week. There
> may also be other, more subtle ways mine is broken.
>
> It also may be that the problem is inherently unsolvable for some
> values. (I'm still waiting for someone with sufficient math ability
> to swoop in and either provide a way that works for all values, or
> confirm that there are just some unavoidable pathological cases.)
>
> John
I was thinking about this problem today. What is needed is to generate
all matches between n players in an order such that any sequence of
(n//2-1) matches does not repeat any player. If there are an even
number of players, this guarantees an even distribution of byes as well
(i.e. a difference of at most 1 between the highest and lowest number of
byes). Unfortunately, if there are an odd number of players, I don't
think this is achievable because there are two sources of byes
unbalance:
* a player needs to be left out of each 'complete round' (where each
player plays each other'
* some players are left out of each weekly round because there are not
enough tennis courts for a complete round to be played in one week.
What I believe is achievable in the case of an odd number of players is
a difference of at most two between the highest and the lowest number of
byes for any player at any point in the tournament.
I don't have a proof of this because I haven't had the time to think
about it for long enough, but I have a toy implementation which I have
tested in a very limited manner. I think it will generate tournaments
with the property that bye imbalance never exceeds 2. I also think it is
not possible to achieve better in general (it's a conjecture!).
----------------------------------------
from itertools import count
def matches(players):
"Generates all matches between players"
n = len(players)
if n % 2:
for i in xrange(n):
for j in xrange(1, 1 + n/2):
yield players[(i+j)%n], players[(i-j)%n]
else:
m = n - 1
for i in xrange(m):
yield players[-1], players[i]
for j in xrange(1, n/2):
yield players[(i+j)%m], players[(i-j)%m]
def print_matches(players):
for line in zip(*matches(players)):
print ' '.join(line)
def tournament(players, courts, nrounds=None):
"""
players: list of players
courts: list of courts
nrounds: number of rounds needed or
"""
if nrounds is None:
rounds = count(1)
else:
rounds = xrange(1, nrounds + 1)
opponents = defaultdict(list)
courts = courts[:len(players)/2]
get_match = matches(players).next
try:
for round in rounds:
print '-'*10
print 'Round', round
for court in courts:
p1, p2 = get_match()
print 'Court %s: %s - %s' % (court, p1, p2)
except StopIteration:
print "All matches played"
----------------------------------------
Example:
>>> players = ['Ann', 'Bea', 'Clo', 'Dee', 'Evi', 'Fae', 'Gil', 'Haz']
>>> courts = ['One', 'Two', 'Three']
>>> tournament(players, courts, 4)
----------
Round 1
Court One: Haz - Ann
Court Two: Bea - Gil
Court Three: Clo - Fae
----------
Round 2
Court One: Dee - Evi
Court Two: Haz - Bea
Court Three: Clo - Ann
----------
Round 3
Court One: Dee - Gil
Court Two: Evi - Fae
Court Three: Haz - Clo
----------
Round 4
Court One: Dee - Bea
Court Two: Evi - Ann
Court Three: Fae - Gil
HTH
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
