Re: Code works fine except...
John Yeung gallium.arsen...@gmail.com writes: On May 5, 11:37 pm, Ross ross.j...@gmail.com wrote: On May 5, 10:33 am, MRAB goo...@mrabarnett.plus.com wrote: Here's my approach (incomplete): FYI... I was testing your code further and discovered a strange outcome... when there are 16 people for 7 courts, every 7th round your code produces 4 byes instead of the correct 2 byes. Well, MRAB did say his was incomplete, and it's significantly shorter and cleaner than mine. Mine has even weirder-looking behavior at 16 players on 7 courts, but I think it's because mine tries harder to keep things balanced. After a few rounds, the inequalities start to build up, and my routine picks some people more often to catch up, but it doesn't prevent the same person from being scheduled for multiple matches the same week. There may also be other, more subtle ways mine is broken. It also may be that the problem is inherently unsolvable for some values. (I'm still waiting for someone with sufficient math ability to swoop in and either provide a way that works for all values, or confirm that there are just some unavoidable pathological cases.) John I was thinking about this problem today. What is needed is to generate all matches between n players in an order such that any sequence of (n//2-1) matches does not repeat any player. If there are an even number of players, this guarantees an even distribution of byes as well (i.e. a difference of at most 1 between the highest and lowest number of byes). Unfortunately, if there are an odd number of players, I don't think this is achievable because there are two sources of byes unbalance: * a player needs to be left out of each 'complete round' (where each player plays each other' * some players are left out of each weekly round because there are not enough tennis courts for a complete round to be played in one week. What I believe is achievable in the case of an odd number of players is a difference of at most two between the highest and the lowest number of byes for any player at any point in the tournament. I don't have a proof of this because I haven't had the time to think about it for long enough, but I have a toy implementation which I have tested in a very limited manner. I think it will generate tournaments with the property that bye imbalance never exceeds 2. I also think it is not possible to achieve better in general (it's a conjecture!). from itertools import count def matches(players): Generates all matches between players n = len(players) if n % 2: for i in xrange(n): for j in xrange(1, 1 + n/2): yield players[(i+j)%n], players[(i-j)%n] else: m = n - 1 for i in xrange(m): yield players[-1], players[i] for j in xrange(1, n/2): yield players[(i+j)%m], players[(i-j)%m] def print_matches(players): for line in zip(*matches(players)): print ' '.join(line) def tournament(players, courts, nrounds=None): players: list of players courts: list of courts nrounds: number of rounds needed or if nrounds is None: rounds = count(1) else: rounds = xrange(1, nrounds + 1) opponents = defaultdict(list) courts = courts[:len(players)/2] get_match = matches(players).next try: for round in rounds: print '-'*10 print 'Round', round for court in courts: p1, p2 = get_match() print 'Court %s: %s - %s' % (court, p1, p2) except StopIteration: print All matches played Example: players = ['Ann', 'Bea', 'Clo', 'Dee', 'Evi', 'Fae', 'Gil', 'Haz'] courts = ['One', 'Two', 'Three'] tournament(players, courts, 4) -- Round 1 Court One: Haz - Ann Court Two: Bea - Gil Court Three: Clo - Fae -- Round 2 Court One: Dee - Evi Court Two: Haz - Bea Court Three: Clo - Ann -- Round 3 Court One: Dee - Gil Court Two: Evi - Fae Court Three: Haz - Clo -- Round 4 Court One: Dee - Bea Court Two: Evi - Ann Court Three: Fae - Gil HTH -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
John Yeung wrote: On May 7, 12:30 am, Ross ross.j...@gmail.com wrote: If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? I certainly have not proved it, but I think you don't need to resort to anything fancy if you are OK with the maximum byes being within two of the minimum byes. (Maybe this needs to be larger with larger numbers of players.) Try using your original shuffle but instead of selecting matches to throw away each week, just use the matches you need (to fill up the courts) and pick up where you left off the next week. For example, with 10 players, each round ideally consists of five matches. If you only have four courts, don't throw away the fifth match; save it as the first match next week. To be honest, I didn't look too carefully at your original shuffle. It may be good enough. It's a little different than the standard rotation as presented on Wikipedia: http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm The one on Wikipedia happened to pass my casual tests with no more than a 2-bye difference between the most-played and least-played players, and didn't run into the problem of scheduling the same player for two matches the same week. But I have to stress I only tried a few starting values, which all worked; I didn't try to break it, or run an extensive battery of tests. It might be an idea to run an exhaustive test on small, but not too small, values in order to see whether the minimum difference can, in fact, be one. If the minimum difference turns out to be two then you might as well stick to a simple algorithm, as long as its minimum difference is two. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 7, 1:11 am, John Yeung gallium.arsen...@gmail.com wrote: On May 7, 12:30 am, Ross ross.j...@gmail.com wrote: If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? I certainly have not proved it, but I think you don't need to resort to anything fancy if you are OK with the maximum byes being within two of the minimum byes. (Maybe this needs to be larger with larger numbers of players.) Try using your original shuffle but instead of selecting matches to throw away each week, just use the matches you need (to fill up the courts) and pick up where you left off the next week. For example, with 10 players, each round ideally consists of five matches. If you only have four courts, don't throw away the fifth match; save it as the first match next week. To be honest, I didn't look too carefully at your original shuffle. It may be good enough. It's a little different than the standard rotation as presented on Wikipedia: http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm The one on Wikipedia happened to pass my casual tests with no more than a 2-bye difference between the most-played and least-played players, and didn't run into the problem of scheduling the same player for two matches the same week. But I have to stress I only tried a few starting values, which all worked; I didn't try to break it, or run an extensive battery of tests. John John, I really appreciate your help with this problem. Thanks to your suggestions, I've managed to solve the problem. Here's what I did: I used my original round_robin generator to generate each week. I then took every week and chained them all together end to end. Then, depending on how many courts are available, I can select that many tuples at a time from the list. If you go in order, the discrepancy between the player with the least amount of byes and the greatest amount of byes is only 1. If you can make it exactly all the way through a cycle, there will be no discrepancy. Anyways, I've done all this by hand and it works so now I'm going to go ahead and code it up. Again, thanks for your help. -Ross -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 7, 8:32 pm, Ross ross.j...@gmail.com wrote: I've managed to solve the problem. If you go in order, the discrepancy between the player with the least amount of byes and the greatest amount of byes is only 1. I don't mean to rain on your parade, but that's not the case for all values. For example, with 7 players and only 1 or 2 courts, there will be weeks in the middle where the bye-difference is 2. This behavior is present in both your shuffle and the standard one in Wikipedia. Ultimately, as it pertains to your physical tennis scheduling with actual courts and actual players, you may never encounter the imbalance. But as a math problem, it's still not solved. (Someone may have solved it or proved it insoluble, but obviously I am not aware of such a proof, because otherwise I would have presented it already.) John -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
John Yeung wrote: On May 5, 11:37 pm, Ross ross.j...@gmail.com wrote: On May 5, 10:33 am, MRAB goo...@mrabarnett.plus.com wrote: Here's my approach (incomplete): FYI... I was testing your code further and discovered a strange outcome... when there are 16 people for 7 courts, every 7th round your code produces 4 byes instead of the correct 2 byes. Well, MRAB did say his was incomplete, and it's significantly shorter and cleaner than mine. Mine has even weirder-looking behavior at 16 players on 7 courts, but I think it's because mine tries harder to keep things balanced. After a few rounds, the inequalities start to build up, and my routine picks some people more often to catch up, but it doesn't prevent the same person from being scheduled for multiple matches the same week. There may also be other, more subtle ways mine is broken. It also may be that the problem is inherently unsolvable for some values. (I'm still waiting for someone with sufficient math ability to swoop in and either provide a way that works for all values, or confirm that there are just some unavoidable pathological cases.) I'm not sure that all the requirements can be met. I have the feeling that if the number of rounds is restricted then the difference between the minimum and maximum number of byes could be 2 because of the requirement that players shouldn't play each other more than once, meaning that the players have to be shuffled around a bit, so a player might play a week earlier or later than would otherwise be the case. If every possible combination is done (everyone plays everyone else) then the number of byes would be the same for all, otherwise the difference could be 2, not 1. I think! :-) -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 10:49 am, Ross ross.j...@gmail.com 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[i].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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 6, 3:29 am, MRAB goo...@mrabarnett.plus.com wrote: I have the feeling that if the number of rounds is restricted then the difference between the minimum and maximum number of byes could be 2 because of the requirement that players shouldn't play each other more than once, meaning that the players have to be shuffled around a bit, so a player might play a week earlier or later than would otherwise be the case. This is the feeling that I am getting also. All my efforts to keep everything as balanced as possible at all times (to be ready for the season to end suddenly at any time) result in messy jams that could otherwise be alleviated if I allowed temporary imbalances, knowing that there are more weeks later to make them up. John -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 6, 3:14 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 6, 3:29 am, MRAB goo...@mrabarnett.plus.com wrote: I have the feeling that if the number of rounds is restricted then the difference between the minimum and maximum number of byes could be 2 because of the requirement that players shouldn't play each other more than once, meaning that the players have to be shuffled around a bit, so a player might play a week earlier or later than would otherwise be the case. This is the feeling that I am getting also. All my efforts to keep everything as balanced as possible at all times (to be ready for the season to end suddenly at any time) result in messy jams that could otherwise be alleviated if I allowed temporary imbalances, knowing that there are more weeks later to make them up. John If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 6, 3:14 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 6, 3:29 am, MRAB goo...@mrabarnett.plus.com wrote: I have the feeling that if the number of rounds is restricted then the difference between the minimum and maximum number of byes could be 2 because of the requirement that players shouldn't play each other more than once, meaning that the players have to be shuffled around a bit, so a player might play a week earlier or later than would otherwise be the case. This is the feeling that I am getting also. All my efforts to keep everything as balanced as possible at all times (to be ready for the season to end suddenly at any time) result in messy jams that could otherwise be alleviated if I allowed temporary imbalances, knowing that there are more weeks later to make them up. John If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 6, 3:14 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 6, 3:29 am, MRAB goo...@mrabarnett.plus.com wrote: I have the feeling that if the number of rounds is restricted then the difference between the minimum and maximum number of byes could be 2 because of the requirement that players shouldn't play each other more than once, meaning that the players have to be shuffled around a bit, so a player might play a week earlier or later than would otherwise be the case. This is the feeling that I am getting also. All my efforts to keep everything as balanced as possible at all times (to be ready for the season to end suddenly at any time) result in messy jams that could otherwise be alleviated if I allowed temporary imbalances, knowing that there are more weeks later to make them up. John If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 7, 12:30 am, Ross ross.j...@gmail.com wrote: If I were to set up a dictionary that counted players used in the bye list and only allowed players to be added to the bye list if they were within 2 of the least used player, would this be a good approach for managing bye selection or would using a dictionary in this manner be unnecessary/redundant? I certainly have not proved it, but I think you don't need to resort to anything fancy if you are OK with the maximum byes being within two of the minimum byes. (Maybe this needs to be larger with larger numbers of players.) Try using your original shuffle but instead of selecting matches to throw away each week, just use the matches you need (to fill up the courts) and pick up where you left off the next week. For example, with 10 players, each round ideally consists of five matches. If you only have four courts, don't throw away the fifth match; save it as the first match next week. To be honest, I didn't look too carefully at your original shuffle. It may be good enough. It's a little different than the standard rotation as presented on Wikipedia: http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm The one on Wikipedia happened to pass my casual tests with no more than a 2-bye difference between the most-played and least-played players, and didn't run into the problem of scheduling the same player for two matches the same week. But I have to stress I only tried a few starting values, which all worked; I didn't try to break it, or run an extensive battery of tests. John -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 1:12 am, John Yeung gallium.arsen...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 12:32 am, John Yeung gallium.arsen...@gmail.com wrote: On May 5, 1:12 am, John Yeung gallium.arsen...@gmail.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
Ross wrote: On May 5, 12:32 am, John Yeung gallium.arsen...@gmail.com wrote: On May 5, 1:12 am, John Yeung gallium.arsen...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 1:33 pm, MRAB goo...@mrabarnett.plus.com wrote: Ross wrote: On May 5, 12:32 am, John Yeung gallium.arsen...@gmail.com wrote: On May 5, 1:12 am, John Yeung gallium.arsen...@gmail.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 10:33 am, MRAB goo...@mrabarnett.plus.com wrote: Ross wrote: On May 5, 12:32 am, John Yeung gallium.arsen...@gmail.com wrote: On May 5, 1:12 am, John Yeung gallium.arsen...@gmail.com 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 FYI... I was testing your code further and discovered a strange outcome... when there are 16 people for 7 courts, every 7th round your code produces 4 byes instead of the correct 2 byes. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 5, 11:37 pm, Ross ross.j...@gmail.com wrote: On May 5, 10:33 am, MRAB goo...@mrabarnett.plus.com wrote: Here's my approach (incomplete): FYI... I was testing your code further and discovered a strange outcome... when there are 16 people for 7 courts, every 7th round your code produces 4 byes instead of the correct 2 byes. Well, MRAB did say his was incomplete, and it's significantly shorter and cleaner than mine. Mine has even weirder-looking behavior at 16 players on 7 courts, but I think it's because mine tries harder to keep things balanced. After a few rounds, the inequalities start to build up, and my routine picks some people more often to catch up, but it doesn't prevent the same person from being scheduled for multiple matches the same week. There may also be other, more subtle ways mine is broken. It also may be that the problem is inherently unsolvable for some values. (I'm still waiting for someone with sufficient math ability to swoop in and either provide a way that works for all values, or confirm that there are just some unavoidable pathological cases.) John -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 3, 10:16 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 3, 11:29 pm, Chris Rebert c...@rebertia.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 7:01 am, Ross ross.j...@gmail.com wrote: On May 3, 10:16 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 3, 11:29 pm, Chris Rebert c...@rebertia.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 3, 8:29 pm, John Machin sjmac...@lexicon.net wrote: On May 4, 12:36 pm, Ross ross.j...@gmail.com 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
Re: Code works fine except...
In article 8d4ec1df-dddb-469a-99a1-695152db7...@n4g2000vba.googlegroups.com, Ross ross.j...@gmail.com 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 (a...@pythoncraft.com) * http://www.pythoncraft.com/ It is easier to optimize correct code than to correct optimized code. --Bill Harlan -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 12:15 pm, a...@pythoncraft.com (Aahz) wrote: In article 8d4ec1df-dddb-469a-99a1-695152db7...@n4g2000vba.googlegroups.com, Ross ross.j...@gmail.com 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 (a...@pythoncraft.com) * 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 10:01 am, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 7:59 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 4, 10:01 am, Ross ross.j...@gmail.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 8:56 pm, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 7:33 pm, John Yeung gallium.arsen...@gmail.com wrote: On May 4, 8:56 pm, Ross ross.j...@gmail.com 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 11:01 pm, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Code works fine except...
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On Sun, May 3, 2009 at 7:36 PM, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 4, 12:36 pm, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 3, 10:36 pm, Ross ross.j...@gmail.com 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code works fine except...
On May 3, 11:29 pm, Chris Rebert c...@rebertia.com 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 -- http://mail.python.org/mailman/listinfo/python-list
