Code works fine except...

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

  1. Ross

    Ross Guest

    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
    #1
    1. Advertising

  2. Ross

    Chris Rebert Guest

    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
    #2
    1. Advertising

  3. Ross

    John Machin Guest

    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
    #3
  4. Ross

    John Yeung Guest

    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
    #4
  5. Ross

    John Yeung Guest

    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
    #5
  6. Ross

    Ross Guest

    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
    #6
  7. Ross

    Ross Guest

    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
    #7
  8. Ross

    Ross Guest

    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
    #8
  9. Ross

    Aahz Guest

    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
     
    Aahz, May 4, 2009
    #9
  10. Ross

    Ross Guest

    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
    #10
  11. Ross

    John Yeung Guest

    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
    #11
  12. Ross

    Ross Guest

    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
    #12
  13. Ross

    John Yeung Guest

    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
    #13
  14. Ross

    Ross Guest

    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
    #14
  15. Ross

    John Yeung Guest

    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
    #15
  16. Ross

    John Yeung Guest

    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
    #16
  17. Ross

    Ross Guest

    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
    #17
  18. Ross

    MRAB Guest

    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:
    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
     
    MRAB, May 5, 2009
    #18
  19. Ross

    Ross Guest

    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:
    >                  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.
     
    Ross, May 5, 2009
    #19
  20. Ross

    John Yeung Guest

    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
    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
     
    John Yeung, May 6, 2009
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Salerno
    Replies:
    20
    Views:
    881
    John Salerno
    Aug 11, 2006
  2. Fabio Z Tessitore

    who is simpler? try/except/else or try/except

    Fabio Z Tessitore, Aug 12, 2007, in forum: Python
    Replies:
    5
    Views:
    397
  3. David House

    try -> except -> else -> except?

    David House, Jul 6, 2009, in forum: Python
    Replies:
    2
    Views:
    363
    Bruno Desthuilliers
    Jul 6, 2009
  4. Peng Yu
    Replies:
    1
    Views:
    561
    Steven D'Aprano
    Nov 18, 2009
  5. MRAB
    Replies:
    0
    Views:
    873
Loading...

Share This Page