Code works fine except...

[Arnaud Delobelle]

John Yeung <gallium.arsenide at gmail.com> writes:

> On May 5, 11:37 pm, Ross <ross.j... at gmail.com> wrote:
>
>> On May 5, 10:33 am, MRAB <goo... at 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