Code works fine except...

[Ross]

[...] the problem may require bigger guns (either much better
math or much more sophisticated programming).
Yes, I'm responding to myself.
Well, I went ahead with the approach I mentioned earlier, generating
all possible matches and then selecting among them as needed to fill
up the courts, trying to keep the number of matches played by each
player as fair as possible.  (I should mention that this, or something
similar, was suggested earlier by someone else in a different thread,
in response to the same question by the same OP.)
I did use "bigger guns" (mainly a class for player objects, with
custom __cmp__ method), but still didn't do anything with doubles.
I haven't tested it much, but I'll post it if anyone's interested.
(That way people can pick on me instead of the OP.
John

I'm interested to see what you did. From your description, it sounds
like I've tried what you've done, but when I implemented my version,
it took minutes to evaluate for bigger numbers. If that isn't the case
with yours, I'd be interested in seeing your implementation.

Here's my approach (incomplete):

def get_pair(player_list, played):
     for first in range(len(player_list)):
         player_1 = player_list[first]
         for second in range(first + 1, len(player_list)):
             player_2 = player_list[second]
             pair = player_1, player_2
             sorted_pair = tuple(sorted(pair))
             if sorted_pair not in played:
                 played.add(sorted_pair)
                 del player_list[second]
                 del player_list[first]
                 return pair
     return None

def round_robin(player_list, courts, played):
     playing = []
     for c in range(courts):
         pair = get_pair(player_list, played)
         if pair is None:
             break
         playing.append(pair)
     byes = player_list[:]
     player_list[:] = byes + [player for pair in playing for player in pair]
     yield playing, byes

def test_round_robin(players, rounds, courts, doubles=False):
     player_list = range(players)
     played = set()
     for r in range(rounds):
         for playing, byes in round_robin(player_list, courts, played):
             print playing, byes

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.

 

[John Yeung]

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

 

[MRAB]

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.)

I'm not sure that all the requirements can be met.

I have the feeling that if the number of rounds is restricted then the
difference between the minimum and maximum number of byes could be 2
because of the requirement that players shouldn't play each other more
than once, meaning that the players have to be shuffled around a bit, so
a player might play a week earlier or later than would otherwise be the
case.

If every possible combination is done (everyone plays everyone else)
then the number of byes would be the same for all, otherwise the
difference could be 2, not 1. I think!

 

[John Yeung]

I have the feeling that if the number of rounds is restricted then the
difference between the minimum and maximum number of byes could be 2
because of the requirement that players shouldn't play each other more
than once, meaning that the players have to be shuffled around a bit, so
a player might play a week earlier or later than would otherwise be the
case.

This is the feeling that I am getting also. All my efforts to keep
everything as balanced as possible at all times (to be ready for the
"season" to end suddenly at any time) result in messy jams that could
otherwise be alleviated if I allowed temporary imbalances, knowing
that there are more weeks later to make them up.

John

 

[Ross]

This is the feeling that I am getting also.  All my efforts to keep
everything as balanced as possible at all times (to be ready for the
"season" to end suddenly at any time) result in messy jams that could
otherwise be alleviated if I allowed temporary imbalances, knowing
that there are more weeks later to make them up.

John

If I were to set up a dictionary that counted players used in the bye
list and only allowed players to be added to the bye list if they were
within 2 of the least used player, would this be a good approach for
managing bye selection or would using a dictionary in this manner be
unnecessary/redundant?

 

[Ross]

This is the feeling that I am getting also.  All my efforts to keep
everything as balanced as possible at all times (to be ready for the
"season" to end suddenly at any time) result in messy jams that could
otherwise be alleviated if I allowed temporary imbalances, knowing
that there are more weeks later to make them up.

John

If I were to set up a dictionary that counted players used in the bye
list and only allowed players to be added to the bye list if they were
within 2 of the least used player, would this be a good approach for
managing bye selection or would using a dictionary in this manner be
unnecessary/redundant?

 

[Ross]

This is the feeling that I am getting also.  All my efforts to keep
everything as balanced as possible at all times (to be ready for the
"season" to end suddenly at any time) result in messy jams that could
otherwise be alleviated if I allowed temporary imbalances, knowing
that there are more weeks later to make them up.

John

If I were to set up a dictionary that counted players used in the bye
list and only allowed players to be added to the bye list if they were
within 2 of the least used player, would this be a good approach for
managing bye selection or would using a dictionary in this manner be
unnecessary/redundant?

 

[John Yeung]

If I were to set up a dictionary that counted players used in the bye
list and only allowed players to be added to the bye list if they were
within 2 of the least used player, would this be a good approach for
managing bye selection or would using a dictionary in this manner be
unnecessary/redundant?

I certainly have not proved it, but I think you don't need to resort
to anything fancy if you are OK with the maximum byes being within two
of the minimum byes. (Maybe this needs to be larger with larger
numbers of players.) Try using your original shuffle but instead of
selecting matches to "throw away" each week, just use the matches you
need (to fill up the courts) and pick up where you left off the next
week. For example, with 10 players, each "round" ideally consists of
five matches. If you only have four courts, don't throw away the
fifth match; save it as the first match next week.

To be honest, I didn't look too carefully at your original shuffle.
It may be good enough. It's a little different than the "standard"
rotation as presented on Wikipedia:

http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

The one on Wikipedia happened to pass my casual tests with no more
than a 2-bye difference between the most-played and least-played
players, and didn't run into the problem of scheduling the same player
for two matches the same week. But I have to stress I only tried a
few starting values, which all worked; I didn't try to break it, or
run an extensive battery of tests.

John

 

[MRAB]

I certainly have not proved it, but I think you don't need to resort
to anything fancy if you are OK with the maximum byes being within two
of the minimum byes. (Maybe this needs to be larger with larger
numbers of players.) Try using your original shuffle but instead of
selecting matches to "throw away" each week, just use the matches you
need (to fill up the courts) and pick up where you left off the next
week. For example, with 10 players, each "round" ideally consists of
five matches. If you only have four courts, don't throw away the
fifth match; save it as the first match next week.

To be honest, I didn't look too carefully at your original shuffle.
It may be good enough. It's a little different than the "standard"
rotation as presented on Wikipedia:

http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

The one on Wikipedia happened to pass my casual tests with no more
than a 2-bye difference between the most-played and least-played
players, and didn't run into the problem of scheduling the same player
for two matches the same week. But I have to stress I only tried a
few starting values, which all worked; I didn't try to break it, or
run an extensive battery of tests.

It might be an idea to run an exhaustive test on small, but not too
small, values in order to see whether the minimum difference can, in
fact, be one. If the minimum difference turns out to be two then you
might as well stick to a simple algorithm, as long as its minimum
difference is two.

 

[Ross]

I certainly have not proved it, but I think you don't need to resort
to anything fancy if you are OK with the maximum byes being within two
of the minimum byes.  (Maybe this needs to be larger with larger
numbers of players.)  Try using your original shuffle but instead of
selecting matches to "throw away" each week, just use the matches you
need (to fill up the courts) and pick up where you left off the next
week.  For example, with 10 players, each "round" ideally consists of
five matches.  If you only have four courts, don't throw away the
fifth match; save it as the first match next week.

To be honest, I didn't look too carefully at your original shuffle.
It may be good enough.  It's a little different than the "standard"
rotation as presented on Wikipedia:

 http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

The one on Wikipedia happened to pass my casual tests with no more
than a 2-bye difference between the most-played and least-played
players, and didn't run into the problem of scheduling the same player
for two matches the same week.  But I have to stress I only tried a
few starting values, which all worked; I didn't try to break it, or
run an extensive battery of tests.

John

John,
I really appreciate your help with this problem. Thanks to your
suggestions, I've managed to solve the problem. Here's what I did: I
used my original round_robin generator to generate each week. I then
took every week and chained them all together end to end. Then,
depending on how many courts are available, I can select that many
tuples at a time from the list. If you go in order, the discrepancy
between the player with the least amount of byes and the greatest
amount of byes is only 1. If you can make it exactly all the way
through a cycle, there will be no discrepancy. Anyways, I've done all
this by hand and it works so now I'm going to go ahead and code it up.
Again, thanks for your help.

-Ross

 

[John Yeung]

I've managed to solve the problem. If you go in
order, the discrepancy between the player with the
least amount of byes and the greatest amount of byes
is only 1.

I don't mean to rain on your parade, but that's not the case for all
values. For example, with 7 players and only 1 or 2 courts, there
will be weeks in the middle where the bye-difference is 2.

This behavior is present in both your shuffle and the standard one in
Wikipedia.

Ultimately, as it pertains to your physical tennis scheduling with
actual courts and actual players, you may never encounter the
imbalance. But as a math problem, it's still not solved. (Someone
may have solved it or proved it insoluble, but obviously I am not
aware of such a proof, because otherwise I would have presented it
already.)

John

 

[Arnaud Delobelle]

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
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