Am I asking for the impossible?

[GoldenOldie]

Hi all. I'm looking for a schedule that will cover a maximum of 4 courts for random doubles pairings and catering for 8 to 20 players. 

When there is an odd number of players or more than 16,  some will have to sit out no more than one round.

Each player must play a maximum of 4 matches, ideally with a different partner and against a different pairing, so ideally no duplicate match ups. Am I asking for the impossible or could this be done?

[Ian Wakeling]

This is more complex than I first thought - since you commented on the thread for the Excel generator I had assumed you were interested in singles play - but doubles play and 4 courts is a much harder problem.

I think your ideal of no duplicate matchups, either as partners or opponents, will only be achieveable if there are 16 or more players.  When this is true you only need to schedule which 4 players to send to a court as they can split into 2 vs 2 any way they like.  Below I have given example schedules for 16 to 18 players, something similar for 19 or 20 players should be possible and I will continue looking, however I don't believe you will find anything useful for less than 16 players.  For example if there are 12 players, then at 1st sight you might think it possible to have everyone matched up with everyone else at least once over 4 rounds on 3 courts, however this is impossible to achieve.

16 players (all players have 4 games each)
      court 1      court 2      court 3      court 4
R1 (16  4  6  7) ( 1  2  3  5) ( 8 12 14 15) ( 9 10 11 13)
R2 (14 11  5  7) ( 8  9  2  4) ( 6  3 13 15) (16  1 10 12)
R3 (13  2 12  7) (14 16  9  3) ( 5 10  4 15) ( 6  8  1 11)
R4 (11 16  2 15) (12  5  6  9) ( 3  8 10  7) ( 4 13 14  1)

17 players (1-13 have 4 games each, 14-17 have 3 games each)

(2 9 7 12) (1 11 14 3) (6 4 5 10) (17 13 8 16)
(13 11 9 10) (4 8 7 3) (17 6 14 2) (12 15 1 5)
(11 4 15 2) (16 12 10 3) (8 5 14 9) (7 1 13 6)
(15 7 17 10) (2 5 3 13) (1 9 4 16) (6 12 11 8)

18 players (1-10 have 4 games each, 11-18 have 3 games each)

(5 15 9 4) (10 3 8 14) (6 17 16 2) (1 13 18 7)
(15 12 6 8) (17 4 3 7) (2 9 11 13) (1 16 10 5)
(5 7 14 2) (8 17 9 1) (6 10 4 11) (16 18 12 3)
(6 13 5 3) (8 2 18 4) (12 9 7 10) (15 14 1 11)

[Ian Wakeling]

Here are some similar schedules for 19 and 20 players hope that helps:

19 players (players 1,2,3,8,12,13,14 have 4 games, the rest have 3 games)
(13 2 8 10) (12 9 18 7) (4 16 14 1) (15 19 3 17)
(8 3 4 11) (2 1 5 7) (13 15 16 12) (6 19 14 9)
(10 9 11 1) (13 17 5 4) (12 3 14 2) (8 15 6 18)
(17 14 7 8) (10 12 5 19) (18 11 16 2) (3 6 13 1)

20 players (players 6,7,12,15 have 4 games, the rest have 3 games)
(8 16 3 7) (15 14 11 20) (17 10 4 12) (1 6 2 5)
(18 10 6 16) (5 7 13 20) (19 14 12 2) (9 15 3 4)
(2 18 17 7) (12 8 9 20) (15 19 16 1) (11 6 4 13)
(13 12 3 1) (8 5 18 15) (17 14 9 6) (19 10 7 11)

[canadave]

Sorry to piggyback on this thread, but I'm looking for something similar and am at my wits' end, so hoping maybe you can help Ian

I'm looking to generate round robin schedules for doubles pickleball, involving from 8 to 40 players, over ideally 7 rounds (but 6 would be fine too). So 32 schedules in all, each one involving a different number of players (from 8 to 40).

My request is similar to GoldenOldie's but not the same, in that I'm looking to *spread around as much as possible* the people on a court. In other words, it would be fine for Player 16 to play on the same court as Player 23 twice or more...as long as it's not a situation where, for example, Player 16 plays on the same court as Player 23 four times, but yet never plays on the same court as Player 5 at all. Ideally everyone should play with as many other people as possible. Currently, with the flawed round robin sheets we use, a player will come off the courts and say "wow, I played on the same court as Bob three times tonight, but never got to play with Jim at all!"

Ideally, too, no player would be "top" more than "bottom" or vice versa. In pickleball, the "top" pairing on a court always starts with the serve, so if our round robin is, for example, six rounds, and Player 1 winds up on "top" for five of those rounds, while Player 2 is on "top" for only one round, that's not fair. "Top" means the first two numbers in the pairing on the court; so, if "1 and 2 play against 3 and 4", then 1 and 2 are on top (and thus start with the serve), and 3 and 4 are on the bottom. So in other words, let's say there's 7 rounds; ideally, in that scenario, players should either be on top four times and bottom three times, or on top three times and on bottom four times. No one should be on top, say, five or more times.

Is THAT doable?

[Ian Wakeling]

Just like the original question in this thread, the more players you have the easier the problem becomes.  And clearly multiples of 4 players are desireable, as having no byes means a further simplification. There are issues that make 7 rounds and 20 players difficult, so I believe the first scenario where it is posisble to have a reasonably nice schedule is for 24 players.  For example I have created the following for 7 rounds (rows) with 6 courts (columns) :

( 4  7  6 24) (11 21  1  2) ( 3 13 17 18) (22 23 16 20) ( 8 12 14 15) (19  5  9 10)
(20  6  9 11) ( 4 14 17 19) ( 7 18  5  8) (10 21 23 24) (15 16  2 13) ( 1  3 12 22)
(22 24 11 18) ( 6  2  8 19) (14 16  3 10) (13 23  1  4) ( 9 12 21  7) (17 20  5 15)
( 2 20  7  3) ( 4 10 11 15) ( 1  5 14 24) ( 9 13 22  8) (17 21  6 16) (19 23 12 18)
(23  2  9 14) (15 18  1  6) ( 8  4  3 21) (17 22  7 10) (13 19 20 24) (12 16  5 11)
( 1  7 16 19) (24  3  9 15) (14 18 20 21) ( 8 11 17 23) ( 2  5  4 22) ( 6 10 12 13)
(17 24  2 12) ( 3  6  5 23) (15 19 21 22) ( 7 11 13 14) ( 1  8 10 20) ( 9 16 18  4)

above if a game is shown as (A B C D), then play the pair AB vs CD, where AB is the top pair and CD is the bottom pair.  If you do this then I think that no two players are on court together more than once, and the top/bottom 3 or 4 times criteria is also met.  I guess I could find something similar for 28,32,36 & 40  players, but it would be too much work to consider the others numbers of players.

[canadave]

Thanks very much for taking the time to do that, Ian--much appreciated

I guess the issue is, although it would definitely be preferable if people showed up in multiples of 4, oftentimes they don't   Would it help the problem if I said the arrangement/distribution of players doesn't have to necessarily be "perfect", but rather it just needs to be "as good as possible"?

In other words, everyone doesn't necessarily need to play with everyone else, there doesn't need to be a precisely perfect distribution of players on top/bottom evenly, byes in the case of numbers of players that are not divisible by 4 are okay, etc. We're just looking for an arrangement that is "better than it currently is"--we currently have situations where some people play on the same court as someone else three times in seven rounds, but never plays with many other players at all. I'm not sure how the round robin sheets we're currently using got generated, but I have to believe there's a way to improve upon them even if it's not perfect distribution in all respects :0

[Ian Wakeling]

"As good as possible" assumes that there is some criterion by which it is possible to measure how good the schedule is - but there are a lot of competing factors here - the number of times pairs of players partner, oppose, or play on the same court together, the number of games and byes each player has, and finally the balance for top/bottom.  These could all be weighted differently, so there is no single best criterion, but the approach you need would be to consider these factors carefully and design a search algorithm to look for an optimal schedule.  Unfortunately, I don't have software that can help here.

I am guessing some of the schedules you have for 4n players, or 4n+1 players, may have been cut down from Whist schedules. If you select any 7 rounds from one of these, this might well leave one pair together three times, while another pair never meets.

If you post the schedule that you have for 14 players, then I will have a look at it, and see if there is any improvement that I can offer.

[canadave]

"As good as possible" assumes that there is some criterion by which it is possible to measure how good the schedule is - but there are a lot of competing factors here - the number of times pairs of players partner, oppose, or play on the same court together, the number of games and byes each player has, and finally the balance for top/bottom.  These could all be weighted differently, so there is no single best criterion, but the approach you need would be to consider these factors carefully and design a search algorithm to look for an optimal schedule.  Unfortunately, I don't have software that can help here.

I am guessing some of the schedules you have for 4n players, or 4n+1 players, may have been cut down from Whist schedules. If you select any 7 rounds from one of these, this might well leave one pair together three times, while another pair never meets.

If you post the schedule that you have for 14 players, then I will have a look at it, and see if there is any improvement that I can offer.

Hi Ian, sorry for the delay in getting back to you.

An example of what I'm talking about is here on these pickleball round robin sheets: RR-Charts.pdf (bendpickleballclub.com) I'm guessing they just used one of the many free round robin generators to generate the schedules for various numbers of players.

If you look at the 14-player sheet, you'll see (for instance) that Player 2 is on the same court as some players once, some players twice, and even plays on the same court as Player 12 THREE times....but never plays on the same court as Player 5.

I guess what I'm not understanding is that this seems to me to be simple from a computational perspective (although I freely admit that since what I'm looking for doesn't seem to currently exist, there' may very well be some factor of difficulty that I'm overlooking). It seems to me that the scheduler should just do this:

• Start in Round 1. For Player 1, search for three other random players to add to the court in that round. Criteria: find the count of how many times Player 1 has played against every other player, then make sure to always pick the three random players from among whom Player 1 has played the least (obviously, in Round 1, Player 1 would not have played anyone, so the three random "other players" could be anybody. However, in later rounds, this pool of available random players would be less and less). This way you won't have Player 1 on the same court as Player 3 a bunch of times, but never played on the same court as Player 12.
• Continue this for all players from 1 to n, where n is the total number of players. If there are any "extra players" at the end of this process (i.e. if n is not divisible by 4), put them down as "byes" who don't play that round...with the caveat that no one who's already had a bye should have ANOTHER bye if there's a player who hasn't had a bye yet.
• Do this for as many rounds as necessary (ideally, for our purposes, 7 rounds).

I know I mentioned other criteria (dividing up who's on top/bottom equally, etc), but even if we could do this minimum thing (have players on the same court as all the other players as equally as possible), that would be an improvement.

[Ian Wakeling]

I had a look at 14 and 12 player sheets in the document that you linked to and I can improve on both of them. Just to be clear I am ignoring top/bottom as suggested.  The new 14 player schedule is optimal, and the 12 player one must be close to being optimal.

For 14 players the 7 round schedule below has all partners different, all opponents different, and all pairs of player on court together either once or twice. Each player has one bye shown in the final column.

  ( 9 3 v 5 2) ( 8 1 v 10 11) (4 13 v 12 7)  (14 6)
  (10 4 v 6 3) ( 9 2 v 11 12) (5 14 v 13 1)  ( 8 7)
  (11 5 v 7 4) (10 3 v 12 13) (6  8 v 14 2)  ( 9 1)
  (12 6 v 1 5) (11 4 v 13 14) (7  9 v  8 3)  (10 2)
  (13 7 v 2 6) (12 5 v 14  8) (1 10 v  9 4)  (11 3)
  (14 1 v 3 7) (13 6 v  8  9) (2 11 v 10 5)  (12 4)
  ( 8 2 v 4 1) (14 7 v  9 10) (3 12 v 11 6)  (13 5)


For 12 players the schedule below has all partners different, all opponents occur once or twice, most pairs of players are on court together either once or twice, however the pairs (7,12), (8,10) and (9,11) occur 3 times.

  (10 2 v 7 8) ( 3 12 v 6 1) (4  9 v 5 11)
  (11 3 v 8 9) ( 1 10 v 4 2) (5  7 v 6 12)
  (12 1 v 9 7) ( 2 11 v 5 3) (6  8 v 4 10)
  ( 6 9 v 2 8) (10  5 v 1 3) (4 11 v 7 12)
  ( 4 7 v 3 9) (11  6 v 2 1) (5 12 v 8 10)
  ( 5 8 v 1 7) (12  4 v 3 2) (6 10 v 9 11)


Regarding the algorithm you have suggested above, I worry it would 'get stuck' before the schedule had filled up, as you would soon find a game where any player that was added would create a problem.  I have had better success with algorithms that start from a randomly generated schedule, and then make iterative improvements by swapping one player for another within a round.

[Ian Wakeling]

I can improve on the 6 round 16 player schedule too, the old version has 13 pairs of players who are never on court together, and one pair (5,16) who meet three times.  In the schedule below all partners are different, all opponents are different, and all pairs of players are on court together either once or twice.

  ( 9 13 v 10 15) (3  7 v 12  1) (14  2 v  4 5) (8 11 v  6 16)
  ( 7 14 v 11 13) (1  8 v 10  2) (15  3 v  5 6) (9 12 v  4 16)
  ( 8 15 v 12 14) (2  9 v 11  3) (13  1 v  6 4) (7 10 v  5 16)
  (10 13 v 12  3) (9 15 v  1  7) ( 6 14 v 16 2) (8  5 v 11  4)
  (11 14 v 10  1) (7 13 v  2  8) ( 4 15 v 16 3) (9  6 v 12  5)
  (12 15 v 11  2) (8 14 v  3  9) ( 5 13 v 16 1) (7  4 v 10  6)

[canadave]

Thanks very much for these improvements Very much appreciated. Is there any programmatic way to try to improve the other sheets?

[Ian Wakeling]

I have been picking off the easy ones above, as they are accessible to a cyclic solution where a small number of base rounds need to be found.  For example the 16 player schedule above is defined by rounds 1 and 4 only, the other rounds are derived by simple permutations.  This does not work all the time, specially for the less symmetric schedules with empty courts.

I have outlined some of the features of a general solution above, it would need to count the frequency of the three types of player pairs, and the frequency of the byes.  Then look for a small change to the schedule that makes the sum of the squares of the frequencies smaller.  You could program this from scratch, or you might be able to set this up in a constraint programming package.

[raydog]

I am in charge of scheduling for a euchre tournament held by a group of fraternity alums each year, where I have dealt with exactly this problem. My constraints are that we have a variable number of people participating each year, and for our initial seeding round I'd like to have as much "mixing" as possible, so (if possible):
1) everyone plays at a table at least once with every other player (either as partner or opponent);
2) if multiple meetings are required, then we don't have pairs which sit together twice while another pair never meets (or one pair meets each other 3 times while another pair hasn't yet met 2 times);
3) no two players are partners twice.

We also have a time constraint, so play exactly 8 rounds (no more, no less).

I have devised schedules for 15 to 36 players using these constraints, and found many of them by using a computer program (rather poorly designed, as I am not a great programmer) running billions of combinations and trying to find the best one. I let some scenarios run for literally weeks! Truly brute force, but it did produce results.

In the end, I was not able to optimize every scenario, but I think I found some pretty reasonable solutions. I was able to avoid any players ever meeting 3 times, but I wasn't always able to have every possible pair of players meet. I calculated the "ideal" situation by comparing the number of actual parings in the tournament (#tables X # rounds) to the number of different possible pairings = n(n-1)/2, where n is the number of players. I presume this ideal is not always achievable, but it gave me a target to shoot for.

I found ideal solutions for 16, 17, 20 and 27+ players.

For the rest, I found the following:
players       never meet (ideal)   never meet (my solution)
    18                     0                                5 
    19                     0                                12
    21                     0                                7
    22                     0                                19
    23                     13                              27
    24                     0                                8
    25                     12                              26
    26                     37                              52

in the case of 15 players, I think I am still far from optimal: I have 18 pairs never meeting and 6 pairs meeting 3 times! Fortunately, we generally have more than 15 players in attendance.

I'd be happy to share these schedules if anyone is interested, but as they are quite specific and would take a long time to type our I prefer to wait for a specific request. Also, if anyone can improve upon my results (as summarized above), please do let me know.

Finally, is there an easy way to generate the solution for 40 players? I know how to generate the perfect solution for 39 rounds (every player partnering with every other player exactly once and opposing every other player exactly twice), but is there a 13 round solution which has every possible pair meeting exactly once [from which I would just take any 8 games]?

Ray                          

[Ian Wakeling]

Hi Ray,

I am thinking about what you have posted and may respond later.   You are of course welcome to post schedules if you would like and you can do this as Excel attachments if that would be more convenient for you.  The 40 player 13 round schedule you are looking for can be found here in the top half of my reply #10.  Or if you want to know how to make it I can find a reference in the mathematical literature for you.

Ian

[Ian Wakeling]

Ray,

I have an observation on your 24 player schedule with 8 never meeting. If you take the schedule in reply #4 above and add the following 8th round:

1  9 17 -
2 10 18 -
3 11 19 -
4 12 20 -
5 13 21 -
6 14 22 -

where "-" represents an unfilled player slot, then the schedule will have only 6 pairs of players who never meet - so improving on your 8 pairs.  To complete the schedule you are free to fill the empty slots with the remaining players 7 8 15 16 23 & 24 in any way you like.

I notice that you don't make any constraints on the byes - I believe I can do better than (26,52), but allowing 2 of the players to have 2 byes allows for better mixing.  Is that acceptable?


Ian