Code works fine except...

R

Ross

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
 
C

Chris Rebert

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
 
J

John Machin

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
 
J

John Yeung

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
 
J

John Yeung

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
 
R

Ross

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

Ross

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

Ross

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
 
A

Aahz

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

John Yeung

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
 
R

Ross

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

John Yeung

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
 
R

Ross

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

John Yeung

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
 
J

John Yeung

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

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

MRAB

Ross said:
[...] 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
 
R

Ross

Ross said:
[...] 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- 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.
 
J

John Yeung

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
from the browser/newsreader.

# 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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top