# Code works fine except...

Discussion in 'Python' started by Ross, May 4, 2009.

1. ### RossGuest

For the past couple weeks, I've been working on an algorithm to
schedule tennis leagues given court constraints and league
considerations (i.e. whether it's a singles or a doubles league). Here
were my requirements when I was designing this algorithm:

-Each player plays against a unique opponent each week.
-Similarly, in a doubles league, each player plays with a unique
partner each week.
-Each player gets a fair number of bye weeks (i.e. the player with the
most bye weeks will have no more than one bye week than the player
with the least number of bye weeks)

I'm very close to arriving at my desired solution, but I have one
glaring flaw. When I have an even number of players sign up for my
league and there are court constraints, my current algorithm gives the
first player in my league a bye week every single week. I'll post my
code below and see how you guys think I should add to/ amend my code.

def round_robin(players, rounds):
if len(players)%2:
players.insert(0, None)
mid = len(players)//2
for i in range(rounds):
yield zip(players[:mid], players[mid:])
players = players[0:1] + players[mid:mid+1] + players[1:mid-1] +
players[mid+1:] + players[mid-1:mid]

def test_round_robin(players, rounds, courts, doubles = False):
players = range(players)
for week in round_robin(players,rounds,courts):
if doubles == True:
doubles_week = len(week)/2.0
byes = doubles_week - courts
if byes == 0:
bye_list = []
else:
bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
playing = [u for u in week if u not in bye_list]
midd = len(playing)//2
doub_sched = zip(playing[:midd], playing[midd:])
print doub_sched, bye_list
else:
byes = len(week)- courts
if byes == 0:
bye_list = []
else:
bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
playing = [u for u in week if u not in bye_list]
print playing, bye_list

Ross, May 4, 2009

2. ### Chris RebertGuest

On Sun, May 3, 2009 at 7:36 PM, Ross <> wrote:
> For the past couple weeks, I've been working on an algorithm to
> schedule tennis leagues given court constraints and league
> considerations (i.e. whether it's a singles or a doubles league). Here
> were my requirements when I was designing this algorithm:
>
> -Each player plays against a unique opponent each week.
> -Similarly, in a doubles league, each player plays with a unique
> partner each week.
> -Each player gets a fair number of bye weeks (i.e. the player with the
> most bye weeks will have no more than one bye week than the player
> with the least number of bye weeks)
>
> I'm very close to arriving at my desired solution, but I have one
> glaring flaw. When I have an even number of players sign up for my
> league and there are court constraints, my current algorithm gives the
> first player in my league a bye week every single week. I'll post my
> code below and see how you guys think I should add to/ amend my code.
>
> def round_robin(players, rounds):
> Â  Â if len(players)%2:
> Â  Â  Â  Â players.insert(0, None)
> Â  Â mid = len(players)//2
> Â  Â for i in range(rounds):
> Â  Â  Â  Â yield zip(players[:mid], players[mid:])
> Â  Â  Â  Â players = players[0:1] + players[mid:mid+1] + players[1:mid-1] +
> players[mid+1:] + players[mid-1:mid]
>
>
> def test_round_robin(players, rounds, courts, doubles = False):
> Â  Â players = range(players)
> Â  Â for week in round_robin(players,rounds,courts):
> Â  Â  Â  Â  Â  Â if doubles == True:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â doubles_week = len(week)/2.0
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â byes = doubles_week - courts
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â if byes == 0:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â bye_list = []
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â else:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â bye_list = week[::int(round(1.072*(courts/byes)+1..08))]
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â playing = [u for u in week if u not in bye_list]
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â midd = len(playing)//2
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â doub_sched = zip(playing[:midd], playing[midd:])
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â print doub_sched, bye_list
> Â  Â  Â  Â  Â  Â else:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â byes = len(week)- courts
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â if byes == 0:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â bye_list = []
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â else:
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â bye_list = week[::int(round(1.072*(courts/byes)+1..08))]
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â playing = [u for u in week if u not in bye_list]
> Â  Â  Â  Â  Â  Â  Â  Â  Â  Â print playing, bye_list

Probably not the cause of the problem, but where did the magic numbers
1.072 and 1.08 come from?

Cheers,
Chris
--
http://blog.rebertia.com

Chris Rebert, May 4, 2009

3. ### John MachinGuest

On May 4, 12:36 pm, Ross <> wrote:
> For the past couple weeks, I've been working on an algorithm to
> schedule tennis leagues given court constraints and league
> considerations (i.e. whether it's a singles or a doubles league). Here
> were my requirements when I was designing this algorithm:
>
> -Each player plays against a unique opponent each week.
> -Similarly, in a doubles league, each player plays with a unique
> partner each week.
> -Each player gets a fair number of bye weeks (i.e. the player with the
> most bye weeks will have no more than one bye week than the player
> with the least number of bye weeks)
>
> I'm very close to arriving at my desired solution, but I have one
> glaring flaw. When I have an even number of players sign up for my
> league and there are court constraints, my current algorithm gives the
> first player in my league a bye week every single week. I'll post my
> code below and see how you guys think I should add to/ amend my code.
>
> def round_robin(players, rounds):
>     if len(players)%2:
>         players.insert(0, None)
>     mid = len(players)//2
>     for i in range(rounds):
>         yield zip(players[:mid], players[mid:])
>         players = players[0:1] + players[mid:mid+1] + players[1:mid-1] +
> players[mid+1:] + players[mid-1:mid]
>
> def test_round_robin(players, rounds, courts, doubles = False):
>     players = range(players)

DON'T change the type/contents/meaning of a variable name like that.
E.g. use "nthings" for a number of things and "things" for a
collection of things.

>     for week in round_robin(players,rounds,courts):

The round_robin() function has only TWO arguments. This code won't
even run.

When you document neither your data structures nor what your functions
are intended to do, the last hope for somebody trying to make sense of
your code is to give meaningful names to your variables. "week" and
"doubles_week" are NOT meaningful.

>             if doubles == True:

Bletch. s/ == True//

>                     doubles_week = len(week)/2.0

I doubt very much that using floating point is a good idea here.

>                     byes = doubles_week - courts
>                     if byes == 0:
>                             bye_list = []
>                     else:
>                             bye_list = week[::int(round(1.072*(courts/byes)+1.08))]

The derivation of the constants 1.072 and 1.08 is .... what?

>                     playing = [u for u in week if u not in bye_list]
>                     midd = len(playing)//2
>                     doub_sched = zip(playing[:midd], playing[midd:])
>                     print doub_sched, bye_list
>             else:
>                     byes = len(week)- courts
>                     if byes == 0:
>                             bye_list = []
>                     else:
>                             bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
>                     playing = [u for u in week if u not in bye_list]
>                     print playing, bye_list

John Machin, May 4, 2009
4. ### John YeungGuest

On May 3, 10:36 pm, Ross <> wrote:

> def round_robin(players, rounds):

[snip]

>
> def test_round_robin(players, rounds, courts, doubles = False):
>     players = range(players)
>     for week in round_robin(players,rounds,courts):

[snip]

First things first: I take it the call to round_robin is only
supposed to take two parameters? Or do you have a version that takes
3?

John

John Yeung, May 4, 2009
5. ### John YeungGuest

On May 3, 11:29 pm, Chris Rebert <> wrote:

> Probably not the cause of the problem, but where
> did the magic numbers 1.072 and 1.08 come from?

It is perhaps not the most direct cause of the problem, in the sense
that the magic numbers could take various values and the problem would
still be there. But the magic numbers appear to be used for
"spreading out" bye selection, and that's broken.

The extended slice as written will always pick the first element,
since the step is guaranteed to be positive. Since the first player
(or None, when there are an odd number of players) stays put in the
first position during the round_robin shuffle, that player will always
be selected for a bye.

Further, as written, the calculated number of byes has no bearing on
the actual number of byes selected.

I think what I would do is adjust the shuffling algorithm in such a
way that everyone moves through the various positions in the list
(would it be as simple as adding a shift at the end of
round_robin???). Then I could simply select the byes from one end of
the list (with a regular slice instead of an extended slice).

John

John Yeung, May 4, 2009
6. ### RossGuest

On May 3, 10:16 pm, John Yeung <> wrote:
> On May 3, 11:29 pm, Chris Rebert <> wrote:
>
> > Probably not the cause of the problem, but where
> > did the magic numbers 1.072 and 1.08 come from?

>
> It is perhaps not the most direct cause of the problem, in the sense
> that the magic numbers could take various values and the problem would
> still be there.  But the magic numbers appear to be used for
> "spreading out" bye selection, and that's broken.
>
> The extended slice as written will always pick the first element,
> since the step is guaranteed to be positive.  Since the first player
> (or None, when there are an odd number of players) stays put in the
> first position during the round_robin shuffle, that player will always
> be selected for a bye.
>
> Further, as written, the calculated number of byes has no bearing on
> the actual number of byes selected.
>
> I think what I would do is adjust the shuffling algorithm in such a
> way that everyone moves through the various positions in the list
> (would it be as simple as adding a shift at the end of
> round_robin???).  Then I could simply select the byes from one end of
> the list (with a regular slice instead of an extended slice).
>
> John

The "magic numbers" that everyone is wondering about are indeed used
for spreading out the bye selection and I got them by simply
calculating a line of best fit when plotting several courts: byes
ratios.

The "byes = #whatever" in my code calculate the number of tuples that
need to be placed in the bye_list.

At first glance, the suggestion of adding a simple shift at the end of
round_robin doesn't seem to work since round_robin already shifts
everything except for the first position already. Please correct me if
I'm wrong because you might have been suggesting something different.

Ross, May 4, 2009
7. ### RossGuest

On May 4, 7:01 am, Ross <> wrote:
> On May 3, 10:16 pm, John Yeung <> wrote:
>
>
>
> > On May 3, 11:29 pm, Chris Rebert <> wrote:

>
> > > Probably not the cause of the problem, but where
> > > did the magic numbers 1.072 and 1.08 come from?

>
> > It is perhaps not the most direct cause of the problem, in the sense
> > that the magic numbers could take various values and the problem would
> > still be there.  But the magic numbers appear to be used for
> > "spreading out" bye selection, and that's broken.

>
> > The extended slice as written will always pick the first element,
> > since the step is guaranteed to be positive.  Since the first player
> > (or None, when there are an odd number of players) stays put in the
> > first position during the round_robin shuffle, that player will always
> > be selected for a bye.

>
> > Further, as written, the calculated number of byes has no bearing on
> > the actual number of byes selected.

>
> > I think what I would do is adjust the shuffling algorithm in such a
> > way that everyone moves through the various positions in the list
> > (would it be as simple as adding a shift at the end of
> > round_robin???).  Then I could simply select the byes from one end of
> > the list (with a regular slice instead of an extended slice).

>
> > John

>
> The "magic numbers" that everyone is wondering about are indeed used
> for spreading out the bye selection and I got them by simply
> calculating a line of best fit when plotting several courts: byes
> ratios.
>
> The "byes = #whatever" in my code calculate the number of tuples that
> need to be placed in the bye_list.
>
> At first glance, the suggestion of adding a simple shift at the end of
> round_robin doesn't seem to work since round_robin already shifts
> everything except for the first position already. Please correct me if
> I'm wrong because you might have been suggesting something different.

And also, as you all have pointed out, my inclusion of

> def test_round_robin(players, rounds, courts, doubles = False):
> players = range(players)
> for week in round_robin(players,rounds,courts):

should have been

> def test_round_robin(players, rounds, courts, doubles = False):
> players = range(players)
> for week in round_robin(players,rounds):

I forgot to erase that extra parameter when I was playing around with
my code.

Ross, May 4, 2009
8. ### RossGuest

On May 3, 8:29 pm, John Machin <> wrote:
> On May 4, 12:36 pm, Ross <> wrote:
>
>
>
> > For the past couple weeks, I've been working on an algorithm to
> > schedule tennis leagues given court constraints and league
> > considerations (i.e. whether it's a singles or a doubles league). Here
> > were my requirements when I was designing this algorithm:

>
> > -Each player plays against a unique opponent each week.
> > -Similarly, in a doubles league, each player plays with a unique
> > partner each week.
> > -Each player gets a fair number of bye weeks (i.e. the player with the
> > most bye weeks will have no more than one bye week than the player
> > with the least number of bye weeks)

>
> > I'm very close to arriving at my desired solution, but I have one
> > glaring flaw. When I have an even number of players sign up for my
> > league and there are court constraints, my current algorithm gives the
> > first player in my league a bye week every single week. I'll post my
> > code below and see how you guys think I should add to/ amend my code.

>
> > def round_robin(players, rounds):
> >     if len(players)%2:
> >         players.insert(0, None)
> >     mid = len(players)//2
> >     for i in range(rounds):
> >         yield zip(players[:mid], players[mid:])
> >         players = players[0:1] + players[mid:mid+1] + players[1:mid-1] +
> > players[mid+1:] + players[mid-1:mid]

>
> > def test_round_robin(players, rounds, courts, doubles = False):
> >     players = range(players)

>
> DON'T change the type/contents/meaning of a variable name like that.
> E.g. use "nthings" for a number of things and "things" for a
> collection of things.
>
> >     for week in round_robin(players,rounds,courts):

>
> The round_robin() function has only TWO arguments. This code won't
> even run.
>
> When you document neither your data structures nor what your functions
> are intended to do, the last hope for somebody trying to make sense of
> your code is to give meaningful names to your variables. "week" and
> "doubles_week" are NOT meaningful.
>
> >             if doubles == True:

>
> Bletch. s/ == True//
>
> >                     doubles_week = len(week)/2.0

>
> I doubt very much that using floating point is a good idea here.
>
> >                     byes = doubles_week - courts
> >                     if byes == 0:
> >                             bye_list = []
> >                     else:
> >                             bye_list = week[::int(round(1.072*(courts/byes)+1.08))]

>
> The derivation of the constants 1.072 and 1.08 is .... what?
>
> >                     playing = [u for u in week if u not in bye_list]
> >                     midd = len(playing)//2
> >                     doub_sched = zip(playing[:midd], playing[midd:])
> >                     print doub_sched, bye_list
> >             else:
> >                     byes = len(week)- courts
> >                     if byes == 0:
> >                             bye_list = []
> >                     else:
> >                             bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
> >                     playing = [u for u in week if u not in bye_list]
> >                     print playing, bye_list

For everybody's enlightenment, I have gone through and commented my
code so you can better understand what I'm doing. Here it is:

def round_robin(players, rounds):
# if number of players odd, insert None at first position
if len(players)%2:
players.insert(0, None)
mid = len(players)//2
for i in range(rounds):
yield zip(players[:mid], players[mid:])
players = players[0:1] + players[mid:mid+1] + players[1:mid-1] +
players[mid+1:] + players[mid-1:mid]
""" rotates players like this: 1 2 -> 3 -> 4

/ |

5 <- 6 <-7 <- 8 """

def test_round_robin(players, rounds, courts, doubles = False):
players = range(players)
for week in round_robin(players,rounds):
if doubles == True: #for doubles pairings
doubles_week = len(week)/2.0
byes = doubles_week - courts #number of tuples to be put into
bye_list
if byes == 0:
bye_list = []
else: """ following formula equally spaces out tuples selected
for bye_list and selects appropriate number according to length of the
league"""
bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
playing = [u for u in week if u not in bye_list]
midd = len(playing)//2
doub_sched = zip(playing[:midd], playing[midd:])#matches the
remaining tuples into doubles matches
print doub_sched, bye_list
else:
byes = len(week)- courts
if byes == 0:
bye_list = []
else:
bye_list = week[::int(round(1.072*(courts/byes)+1.08))]
playing = [u for u in week if u not in bye_list]
print playing, bye_list

Ross, May 4, 2009
9. ### AahzGuest

In article <>,
Ross <> wrote:
>
>def test_round_robin(players, rounds, courts, doubles = False):
> players = range(players)
> for week in round_robin(players,rounds,courts):
> if doubles == True:
> doubles_week = len(week)/2.0
> byes = doubles_week - courts

Side note: thou shalt indent four spaces, no more, no fewer

--
Aahz () <*> http://www.pythoncraft.com/

"It is easier to optimize correct code than to correct optimized code."
--Bill Harlan

Aahz, May 4, 2009
10. ### RossGuest

On May 4, 12:15 pm, (Aahz) wrote:
> In article <>,
>
> Ross  <> wrote:
>
> >def test_round_robin(players, rounds, courts, doubles = False):
> >    players = range(players)
> >    for week in round_robin(players,rounds,courts):
> >        if doubles == True:
> >                doubles_week = len(week)/2.0
> >                byes = doubles_week - courts

>
> Side note: thou shalt indent four spaces, no more, no fewer
>
> For more info, see PEP 8.
> --
> Aahz ()           <*>        http://www.pythoncraft.com/
>
> "It is easier to optimize correct code than to correct optimized code."
> --Bill Harlan

Yes... I know this. Unfortunately, copy/pasting my code from the IDE
into the google group messes with indentations.

Ross, May 4, 2009
11. ### John YeungGuest

On May 4, 10:01 am, Ross <> wrote:
> The "magic numbers" that everyone is wondering about are
> indeed used for spreading out the bye selection and I got
> them by simply calculating a line of best fit when plotting
> several courts: byes ratios.

But that doesn't really help you. When you do seq[::step], step is
evaluated once and used for the whole extended slice. So in almost
all cases that you are likely to encounter, step is 2, so you'll get
seq[0], seq[2], seq[4], etc. Even if step is some other positive
number, seq[0] will always be chosen.

> The "byes = #whatever" in my code calculate the number of
> tuples that need to be placed in the bye_list.

Fine, but that's not the number of byes that you put into bye_list.

> At first glance, the suggestion of adding a simple shift
> at the end of round_robin doesn't seem to work since
> round_robin already shifts everything except for the first
> position already. Please correct me if I'm wrong because
> you might have been suggesting something different.

If you read my post carefully, you would see that you HAVE to do
something about the first player always being stuck in the first
spot. Either move him around, or select your byes differently.

That said, I've played around with the shuffling a bit, and it does
seem to be pretty tricky to get it to work for the general case where
there is no prior knowledge of how many players and courts you will
have.

I can't shake the feeling that someone good at math will be able to
figure out something elegant; but if left to my own devices, I am
starting to lean toward just generating all the possible matches and
somehow picking from them as needed to fill the courts, trying to keep
the number of matches played by each player as close to equal as
possible, and trying to keep the waiting times approximately equal as
well.

John

John Yeung, May 5, 2009
12. ### RossGuest

On May 4, 7:59 pm, John Yeung <> wrote:
> On May 4, 10:01 am, Ross <> wrote:
>
> > The "magic numbers" that everyone is wondering about are
> > indeed used for spreading out the bye selection and I got
> > them by simply calculating a line of best fit when plotting
> > several courts: byes ratios.

>
> But that doesn't really help you.  When you do seq[::step], step is
> evaluated once and used for the whole extended slice.  So in almost
> all cases that you are likely to encounter, step is 2, so you'll get
> seq[0], seq[2], seq[4], etc.  Even if step is some other positive
> number, seq[0] will always be chosen.
>
> > The "byes = #whatever" in my code calculate the number of
> > tuples that need to be placed in the bye_list.

>
> Fine, but that's not the number of byes that you put into bye_list.
>
> > At first glance, the suggestion of adding a simple shift
> > at the end of round_robin doesn't seem to work since
> > round_robin already shifts everything except for the first
> > position already. Please correct me if I'm wrong because
> > you might have been suggesting something different.

>
> If you read my post carefully, you would see that you HAVE to do
> something about the first player always being stuck in the first
> spot.  Either move him around, or select your byes differently.
>
> That said, I've played around with the shuffling a bit, and it does
> seem to be pretty tricky to get it to work for the general case where
> there is no prior knowledge of how many players and courts you will
> have.
>
> I can't shake the feeling that someone good at math will be able to
> figure out something elegant; but if left to my own devices, I am
> starting to lean toward just generating all the possible matches and
> somehow picking from them as needed to fill the courts, trying to keep
> the number of matches played by each player as close to equal as
> possible, and trying to keep the waiting times approximately equal as
> well.
>
> John

"But that doesn't really help you. When you do seq[::step], step is
evaluated once and used for the whole extended slice. So in almost
all cases that you are likely to encounter, step is 2, so you'll get
seq[0], seq[2], seq[4], etc. Even if step is some other positive
number, seq[0] will always be chosen."

It's not true that in almost all cases the step is 2. How that is
evaluated directly depends on the number of available courts. Anyways,
you're right that seq[0] is always evaluated. That's why my algorithm
works fine when there are odd numbers of players in a league. But if
you will notice, my original question was how I could ADD TO or AMMEND
my current code to account for even number of players. I have used an
algorithm that comes up with all possible pairings and then randomly
puts people together each week and places players in a bye list
according to how many times they've previously been in the bye list
but since I was dealing with random permutations, the algorithm took
minutes to evaluate when there were more than 10 players in the
league.

Ross, May 5, 2009
13. ### John YeungGuest

On May 4, 8:56 pm, Ross <> wrote:

> Anyways, you're right that seq[0] is always evaluated.
> That's why my algorithm works fine when there are odd
> numbers of players in a league.

It doesn't work fine for all odd numbers of players. For example, 15
players on 3 courts should result in 5 byes. But what actually
happens with your code is that you get 4 byes or 8 byes, depending on
whether you've got floating-point division enabled.

So the way you are selecting byes does not even guarantee that you'll
allocate the correct number of active matches for the number of
courts, and this is due to the fact that the extended slice is too
"coarse" a tool for the task. Now, it may be that for you, the number
of players and courts is always within a confined range such that
extended slicing and your magic constants will work. That's fine for
you, but we weren't given that information.

I haven't even begun to look at what happens for doubles.

John

John Yeung, May 5, 2009
14. ### RossGuest

On May 4, 7:33 pm, John Yeung <> wrote:
> On May 4, 8:56 pm, Ross <> wrote:
>
> > Anyways, you're right that seq[0] is always evaluated.
> > That's why my algorithm works fine when there are odd
> > numbers of players in a league.

>
> It doesn't work fine for all odd numbers of players.  For example, 15
> players on 3 courts should result in 5 byes.  But what actually
> happens with your code is that you get 4 byes or 8 byes, depending on
> whether you've got floating-point division enabled.
>
> So the way you are selecting byes does not even guarantee that you'll
> allocate the correct number of active matches for the number of
> courts, and this is due to the fact that the extended slice is too
> "coarse" a tool for the task.  Now, it may be that for you, the number
> of players and courts is always within a confined range such that
> extended slicing and your magic constants will work.  That's fine for
> you, but we weren't given that information.
>
> I haven't even begun to look at what happens for doubles.
>
> John

You're right... I only tested cases when number of people playing
outnumbered the number of byes that week. Anyways, I'm new to
programming and this has been a good learning experience. Next time
around, I'll be sure to thoroughly comment my code before I ask for
help on it. I really appreciate all the help that you've offered so
far. Right now, I'm debating whether I should try to reinvent the
round_robin generator part of the code or whether there still might be
a way to shuffle the results of the generated output so that I can
slice it effectively.

Ross, May 5, 2009
15. ### John YeungGuest

On May 4, 11:01 pm, Ross <> wrote:
> Anyways, I'm new to
> programming and this has been a good learning experience.

I'm glad that you've been trying, and seem to be sticking it out
despite sometimes getting negative feedback here.

> Next time around, I'll be sure to thoroughly comment
> my code before I ask for help on it.

The best documentation, especially for a language like Python, is
simply logical variable names and sensible conventions. I bring this
up because I'm wary of the word "thoroughly". When you're dealing
with experts, it's actually best to use inline comments sparingly;
they can figure out what code does. The overall problem description
at the top is important, as well as explanation of "magic numbers" and
such.

> I really appreciate all the help that you've offered so far.

You're welcome. I'm not sure how much I've helped, especially as I'm
frankly not one of the stronger programmers here.

> Right now, I'm debating whether I should try to reinvent
> the round_robin generator part of the code or whether
> there still might be a way to shuffle the results of the
> generated output so that I can slice it effectively.

If you are going to typically have roughly enough courts for your
players (as implied by your test data), then maybe there's still a
chance for using extended slicing. Just make sure you don't always
pick the first element. If the number of players and the number of
courts can vary wildly, and won't always match up at least sort of
nicely, then the problem may require bigger guns (either much better
math or much more sophisticated programming).

John

John Yeung, May 5, 2009
16. ### John YeungGuest

On May 5, 1:12 am, John Yeung <> wrote:

> [...] 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

John Yeung, May 5, 2009
17. ### RossGuest

On May 5, 12:32 am, John Yeung <> wrote:
> On May 5, 1:12 am, John Yeung <> wrote:
>
> > [...] 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.

Ross, May 5, 2009
18. ### MRABGuest

Ross wrote:
> On May 5, 12:32 am, John Yeung <> wrote:
>> On May 5, 1:12 am, John Yeung <> wrote:
>>
>>> [...] 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:
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

MRAB, May 5, 2009
19. ### RossGuest

On May 5, 1:33 pm, MRAB <> wrote:
> Ross wrote:
> > On May 5, 12:32 am, John Yeung <> wrote:
> >> On May 5, 1:12 am, John Yeung <> wrote:

>
> >>> [...] 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:
>                  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- Hide quoted text -
>
> - Show quoted text -

Looks like somewhat of an improvement, although the bye distribution
is still slightly lopsided. For example, in a singles league with 12
players, 12 rounds, and 4 courts, The first player had at least 2 less
byes than every other player and 3 less byes than the players with the
most number of byes. Thanks for your input though...I'll look into how
I can improve upon it.

Ross, May 5, 2009
20. ### John YeungGuest

On May 5, 10:49 am, Ross <> wrote:
> 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.

I don't know how big your "bigger numbers" are, but this should run in
a reasonable time. It helps if you are using Python 2.6. If not, you
should go on-line to the itertools docs to get the pure-Python
equivalent for itertools.combinations.

Since no matches are "thrown away", the byes are expressed simply as a
list of players that have to sit out for the week.

A couple of the lines are on the longish side, so beware of wrapping

# Let's just try choosing from the possible combinations, each week
# scheduling those who have played the least or waited the longest.

import itertools

class Player(object):
def __init__(self, id):
self.id = id
self.played = []
self.latency = 0

def __str__(self):
str(self.id)

def __cmp__(self, other):
if len(self.played) != len(other.played):
return len(self.played) - len(other.played)
return other.latency - self.latency # select longer latency
first

def flattened(listOfLists):
return list(itertools.chain(*listOfLists))

def pairings(players):
idlist = range(players)
playerlist = [Player(i) for i in idlist]
matchlist = list(itertools.combinations(idlist, 2))
while matchlist:
found = False
playerlist.sort()
for i in range(players - 1):
for j in range(i + 1, players):
candidate = tuple(sorted((playerlist.id, playerlist
[j].id)))
if candidate in matchlist:
yield matchlist.pop(matchlist.index(candidate))
for p in playerlist:
if p.id == candidate[0]:
p.played.append(candidate[1])
p.latency = 0
elif p.id == candidate[1]:
p.played.append(candidate[0])
p.latency = 0
else:
p.latency += 1
found = True
break
if found: break

def schedule(players, weeks, courts):
playerlist = range(players)
matchlist = list(pairings(players))
cap = min(courts, players // 2)
start = 0
for week in range(weeks):
matches = matchlist[start:start + cap]
byes = set(playerlist) - set(flattened(matches))
print matches, list(byes)
start += cap

John Yeung, May 6, 2009