My friend Steve asked for help in creating a schedule for a round-robin rotating-partners doubles pickleball tournament with 8 to 16 players using multiple courts. In this type of tournament:
If there are P players then everyone should partner with the P-1 other players one time each and play P-1 games. There are P×(P-1)/2 total pairs of players, and the problem is that if this number is odd, the pairs cannot be evenly scheduled into games with two pairs per game. In that case (which happens when neither P nor P-1 is divisible by 4), two players will have to partner with each other a second time, and they will play one more game than everyone else.
Below are the best schedules I could come up with. For each tournament I give two tables, the first listing the games scheduled in each round on each court, and the second counting how many times each player plays against each opponent. (As mentioned above, it is best when these counts are all 2.)
This schedule is perfect in the sense that it meets all the constraints exactly:
Round | Court 1 | Court 2 |
---|---|---|
1 | 1,6 vs 2,4 | 3,5 vs 7,8 |
2 | 1,5 vs 3,6 | 2,8 vs 4,7 |
3 | 2,3 vs 6,8 | 4,5 vs 1,7 |
4 | 4,6 vs 3,7 | 1,2 vs 5,8 |
5 | 1,8 vs 6,7 | 3,4 vs 2,5 |
6 | 2,6 vs 5,7 | 1,4 vs 3,8 |
7 | 2,7 vs 1,3 | 4,8 vs 5,6 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Total | |
---|---|---|---|---|---|---|---|---|---|
1 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 |
2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 7 |
3 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 7 |
4 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 7 |
5 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 7 |
6 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 7 |
7 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 7 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 7 |
This is an imperfect schedule as indicated by the "Summary of counts: 28 twice; 4 thrice; 4 once"–a perfect schedule would have "36 twice".
Round | Court 1 | Court 2 |
---|---|---|
1 | 8,9 vs 1,6 | 2,4 vs 5,7 |
2 | 6,7 vs 5,9 | 1,4 vs 3,8 |
3 | 4,7 vs 3,9 | 2,5 vs 1,8 |
4 | 1,5 vs 7,8 | 2,9 vs 3,6 |
5 | 6,9 vs 4,5 | 1,3 vs 2,7 |
6 | 3,7 vs 6,8 | 4,9 vs 1,2 |
7 | 1,9 vs 3,5 | 2,6 vs 4,8 |
8 | 1,7 vs 4,6 | 5,8 vs 2,3 |
9 | 7,9 vs 2,8 | 5,6 vs 3,4 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Total | |
---|---|---|---|---|---|---|---|---|---|---|
1 | - | 2 | 2 | 2 | 2 | 1 | 2 | 3 | 2 | 8 |
2 | 2 | - | 2 | 2 | 2 | 1 | 2 | 3 | 2 | 8 |
3 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 8 |
4 | 2 | 2 | 2 | - | 2 | 3 | 2 | 1 | 2 | 8 |
5 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 8 |
6 | 1 | 1 | 2 | 3 | 2 | - | 2 | 2 | 3 | 8 |
7 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 8 |
8 | 3 | 3 | 2 | 1 | 2 | 2 | 2 | - | 1 | 8 |
9 | 2 | 2 | 2 | 2 | 2 | 3 | 2 | 1 | - | 8 |
With 10 players, there are 10×9/2 = 45 pairs of partners, an odd numbers. We arbitrarily decide to make players 1 and 2 partner with each other twice, and play an extra game.
The following schedule takes the minimum number of rounds and is fairly well-balanced in terms of opponent counts:
Round | Court 1 | Court 2 |
---|---|---|
1 | 1,2 vs 3,4 | 7,9 vs 5,6 |
2 | 2,6 vs 5,8 | 3,10 vs 4,7 |
3 | 3,8 vs 1,9 | 4,10 vs 2,5 |
4 | 6,7 vs 1,2 | 8,9 vs 3,5 |
5 | 1,7 vs 2,8 | 3,6 vs 5,10 |
6 | 1,6 vs 9,10 | 7,8 vs 4,5 |
7 | 2,7 vs 3,9 | 4,8 vs 6,10 |
8 | 1,10 vs 5,7 | 2,4 vs 6,9 |
9 | 8,10 vs 4,9 | 1,5 vs 2,3 |
10 | 3,7 vs 6,8 | 1,4 vs 5,9 |
11 | 2,9 vs 7,10 | 1,3 vs 4,6 |
12 | 1,8 vs 2,10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 10 |
2 | 3 | - | 2 | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 10 |
3 | 3 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 9 |
4 | 2 | 2 | 2 | - | 2 | 2 | 1 | 2 | 2 | 3 | 9 |
5 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 9 |
6 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 9 |
7 | 2 | 3 | 2 | 1 | 2 | 2 | - | 2 | 2 | 2 | 9 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 9 |
9 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 9 |
10 | 2 | 2 | 1 | 3 | 2 | 2 | 2 | 2 | 2 | - | 9 |
Again, with 11 players, 1 and 2 will play an extra game:
Round | Court 1 | Court 2 |
---|---|---|
1 | 1,2 vs 3,11 | 7,8 vs 6,10 |
2 | 7,10 vs 1,11 | 6,8 vs 2,4 |
3 | 1,2 vs 9,11 | 6,7 vs 3,5 |
4 | 1,6 vs 2,3 | 4,9 vs 5,7 |
5 | 2,9 vs 4,10 | 3,6 vs 7,11 |
6 | 1,7 vs 2,8 | 9,10 vs 3,4 |
7 | 8,9 vs 6,11 | 2,5 vs 3,10 |
8 | 1,10 vs 4,6 | 5,8 vs 2,7 |
9 | 5,11 vs 6,9 | 4,8 vs 1,3 |
10 | 1,9 vs 3,7 | 2,11 vs 4,5 |
11 | 3,9 vs 8,10 | 5,6 vs 1,4 |
12 | 5,9 vs 1,8 | 10,11 vs 4,7 |
13 | 1,5 vs 2,10 | 4,11 vs 3,8 |
14 | 5,10 vs 8,11 | 7,9 vs 2,6 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
2 | 3 | - | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
3 | 3 | 2 | - | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 10 |
4 | 2 | 2 | 2 | - | 2 | 2 | 1 | 2 | 2 | 3 | 2 | 10 |
5 | 2 | 3 | 1 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 10 |
6 | 2 | 2 | 2 | 2 | 2 | - | 3 | 2 | 2 | 1 | 2 | 10 |
7 | 2 | 2 | 2 | 1 | 2 | 3 | - | 2 | 2 | 2 | 2 | 10 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 10 |
9 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 10 |
10 | 2 | 2 | 2 | 3 | 2 | 1 | 2 | 2 | 2 | - | 2 | 10 |
11 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 10 |
This schedule is imperfect, but has the minimum number of rounds and is very well balanced:
Round | Court 1 | Court 2 |
---|---|---|
1 | 4,12 vs 6,10 | 2,9 vs 3,11 |
2 | 3,6 vs 1,2 | 5,10 vs 7,11 |
3 | 3,9 vs 4,8 | 2,11 vs 5,7 |
4 | 3,5 vs 4,6 | 1,9 vs 10,12 |
5 | 1,5 vs 8,12 | 2,7 vs 6,9 |
6 | 7,10 vs 6,8 | 1,11 vs 4,9 |
7 | 5,9 vs 3,10 | 7,12 vs 2,4 |
8 | 5,12 vs 3,8 | 1,7 vs 9,10 |
9 | 1,4 vs 5,6 | 8,11 vs 9,12 |
10 | 2,8 vs 4,11 | 3,12 vs 6,7 |
11 | 2,12 vs 4,10 | 5,11 vs 1,6 |
12 | 1,8 vs 4,7 | 6,12 vs 9,11 |
13 | 8,9 vs 2,6 | 3,4 vs 10,11 |
14 | 7,9 vs 4,5 | 2,3 vs 1,10 |
15 | 2,10 vs 5,8 | 3,7 vs 11,12 |
16 | 7,8 vs 1,3 | |
17 | 1,12 vs 2,5 | 8,10 vs 6,11 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 11 |
2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
3 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
4 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
5 | 3 | 2 | 2 | 2 | - | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 11 |
6 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
7 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 11 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 2 | 2 | 11 |
9 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | - | 2 | 3 | 2 | 11 |
10 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 11 |
11 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 2 | - | 2 | 11 |
12 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 11 |
If 3 courts are available, this schedule takes the minimum number of rounds:
Round | Court 1 | Court 2 | Court 3 |
---|---|---|---|
1 | 1,2 vs 8,11 | 5,10 vs 3,4 | 7,12 vs 6,9 |
2 | 1,6 vs 2,4 | 5,11 vs 7,10 | 8,9 vs 3,12 |
3 | 6,8 vs 4,9 | 2,3 vs 10,12 | 5,7 vs 1,11 |
4 | 1,5 vs 2,6 | 3,8 vs 4,7 | 9,12 vs 10,11 |
5 | 5,9 vs 2,8 | 3,11 vs 6,10 | 1,7 vs 4,12 |
6 | 1,8 vs 11,12 | 3,5 vs 2,7 | 9,10 vs 4,6 |
7 | 2,10 vs 4,8 | 3,7 vs 1,9 | 5,12 vs 6,11 |
8 | 1,10 vs 2,9 | 8,12 vs 4,5 | 3,6 vs 7,11 |
9 | 3,9 vs 2,11 | 5,6 vs 7,8 | 4,10 vs 1,12 |
10 | 3,10 vs 5,8 | 9,11 vs 1,4 | 2,12 vs 6,7 |
11 | 2,5 vs 4,11 | 1,3 vs 6,12 | 7,9 vs 8,10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 3 | 1 | 3 | 1 | 2 | 2 | 1 | 2 | 1 | 3 | 3 | 11 |
2 | 3 | - | 2 | 2 | 3 | 2 | 1 | 2 | 2 | 2 | 2 | 1 | 11 |
3 | 1 | 2 | - | 1 | 2 | 2 | 3 | 2 | 2 | 3 | 2 | 2 | 11 |
4 | 3 | 2 | 1 | - | 2 | 2 | 1 | 3 | 2 | 3 | 1 | 2 | 11 |
5 | 1 | 3 | 2 | 2 | - | 2 | 3 | 3 | 0 | 2 | 3 | 1 | 11 |
6 | 2 | 2 | 2 | 2 | 2 | - | 3 | 1 | 2 | 1 | 2 | 3 | 11 |
7 | 2 | 1 | 3 | 1 | 3 | 3 | - | 2 | 2 | 1 | 2 | 2 | 11 |
8 | 1 | 2 | 2 | 3 | 3 | 1 | 2 | - | 3 | 2 | 1 | 2 | 11 |
9 | 2 | 2 | 2 | 2 | 0 | 2 | 2 | 3 | - | 3 | 2 | 2 | 11 |
10 | 1 | 2 | 3 | 3 | 2 | 1 | 1 | 2 | 3 | - | 2 | 2 | 11 |
11 | 3 | 2 | 2 | 1 | 3 | 2 | 2 | 1 | 2 | 2 | - | 2 | 11 |
12 | 3 | 1 | 2 | 2 | 1 | 3 | 2 | 2 | 2 | 2 | 2 | - | 11 |
This schedule takes 2 more rounds than minimal, but is much more balanced:
Round | Court 1 | Court 2 | Court 3 |
---|---|---|---|
1 | 1,2 vs 3,4 | 5,6 vs 11,12 | 9,10 vs 7,8 |
2 | 9,11 vs 4,12 | 8,10 vs 2,6 | 1,3 vs 5,7 |
3 | 7,12 vs 2,3 | 5,9 vs 4,6 | 8,11 vs 1,10 |
4 | 2,4 vs 6,11 | 5,12 vs 7,10 | |
5 | 4,7 vs 2,9 | 6,12 vs 3,8 | |
6 | 1,9 vs 2,10 | 3,6 vs 7,11 | 4,5 vs 8,12 |
7 | 5,8 vs 2,12 | 6,7 vs 4,10 | 1,11 vs 3,9 |
8 | 1,12 vs 6,9 | 3,7 vs 4,8 | 5,10 vs 2,11 |
9 | 2,5 vs 1,6 | 3,10 vs 4,9 | |
10 | 3,11 vs 2,8 | 1,5 vs 7,9 | |
11 | 3,12 vs 10,11 | 6,8 vs 1,7 | |
12 | 3,5 vs 6,10 | 9,12 vs 2,7 | 1,8 vs 4,11 |
13 | 5,11 vs 8,9 | 1,4 vs 10,12 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 2 | 2 | 1 | 11 |
2 | 2 | - | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 11 |
3 | 2 | 2 | - | 2 | 1 | 2 | 3 | 2 | 1 | 2 | 3 | 2 | 11 |
4 | 2 | 2 | 2 | - | 1 | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 11 |
5 | 2 | 2 | 1 | 1 | - | 3 | 2 | 2 | 2 | 2 | 2 | 3 | 11 |
6 | 2 | 2 | 2 | 2 | 3 | - | 2 | 2 | 1 | 2 | 2 | 2 | 11 |
7 | 2 | 2 | 3 | 2 | 2 | 2 | - | 2 | 3 | 2 | 0 | 2 | 11 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 1 | 2 | 3 | 2 | 11 |
9 | 3 | 2 | 1 | 3 | 2 | 1 | 3 | 1 | - | 2 | 2 | 2 | 11 |
10 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | - | 2 | 2 | 11 |
11 | 2 | 2 | 3 | 2 | 2 | 2 | 0 | 3 | 2 | 2 | - | 2 | 11 |
12 | 1 | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | - | 11 |
Round | Court 1 | Court 2 | Court 3 | Court 4 |
---|---|---|---|---|
1 | 1,2 vs 3,4 | 10,14 vs 7,8 | 9,13 vs 5,6 | 11,16 vs 12,15 |
2 | 11,15 vs 2,4 | 5,7 vs 6,8 | 9,14 vs 10,13 | 1,3 vs 12,16 |
3 | 13,16 vs 2,3 | 4,10 vs 8,15 | 1,6 vs 11,14 | 7,12 vs 5,9 |
4 | 10,15 vs 2,6 | 3,7 vs 11,13 | 12,14 vs 4,8 | 1,5 vs 9,16 |
5 | 10,16 vs 2,5 | 3,8 vs 9,15 | 6,11 vs 1,14 | 4,7 vs 12,13 |
6 | 11,12 vs 2,8 | 3,5 vs 4,6 | 1,7 vs 9,10 | 13,14 vs 15,16 |
7 | 1,8 vs 2,7 | 13,15 vs 4,5 | 3,6 vs 10,12 | 9,11 vs 14,16 |
8 | 1,9 vs 2,10 | 3,11 vs 8,13 | 4,16 vs 6,12 | 7,14 vs 5,15 |
9 | 7,13 vs 2,9 | 5,16 vs 4,11 | 6,15 vs 3,12 | 1,10 vs 8,14 |
10 | 5,14 vs 2,12 | 3,10 vs 4,9 | 8,16 vs 6,13 | 1,11 vs 7,15 |
11 | 4,12 vs 2,14 | 3,15 vs 6,16 | 1,13 vs 8,9 | 7,10 vs 5,11 |
12 | 5,8 vs 2,16 | 3,13 vs 10,11 | 1,4 vs 6,7 | 9,12 vs 14,15 |
13 | 7,11 vs 2,15 | 1,16 vs 4,13 | 8,12 vs 6,9 | 5,10 vs 3,14 |
14 | 3,9 vs 2,11 | 8,10 vs 4,15 | 6,14 vs 7,16 | 5,13 vs 1,12 |
15 | 2,13 vs 4,14 | 3,16 vs 7,9 | 6,10 vs 1,15 | 8,11 vs 5,12 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | Total | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | - | 2 | 1 | 2 | 1 | 3 | 3 | 2 | 3 | 3 | 2 | 1 | 2 | 2 | 1 | 2 | 15 |
2 | 2 | - | 2 | 3 | 2 | 0 | 2 | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 2 | 15 |
3 | 1 | 2 | - | 2 | 1 | 3 | 1 | 1 | 3 | 3 | 3 | 2 | 3 | 0 | 2 | 3 | 15 |
4 | 2 | 3 | 2 | - | 2 | 2 | 1 | 2 | 0 | 2 | 1 | 3 | 3 | 2 | 3 | 2 | 15 |
5 | 1 | 2 | 1 | 2 | - | 2 | 3 | 2 | 2 | 2 | 2 | 3 | 2 | 2 | 1 | 3 | 15 |
6 | 3 | 0 | 3 | 2 | 2 | - | 2 | 2 | 1 | 2 | 1 | 3 | 1 | 2 | 3 | 3 | 15 |
7 | 3 | 2 | 1 | 1 | 3 | 2 | - | 2 | 3 | 2 | 3 | 1 | 2 | 2 | 2 | 1 | 15 |
8 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | - | 2 | 3 | 2 | 3 | 2 | 2 | 2 | 1 | 15 |
9 | 3 | 2 | 3 | 0 | 2 | 1 | 3 | 2 | - | 3 | 1 | 2 | 3 | 2 | 1 | 2 | 15 |
10 | 3 | 2 | 3 | 2 | 2 | 2 | 2 | 3 | 3 | - | 1 | 0 | 1 | 3 | 3 | 0 | 15 |
11 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 2 | 1 | 1 | - | 2 | 2 | 2 | 3 | 2 | 15 |
12 | 1 | 2 | 2 | 3 | 3 | 3 | 1 | 3 | 2 | 0 | 2 | - | 1 | 3 | 2 | 2 | 15 |
13 | 2 | 2 | 3 | 3 | 2 | 1 | 2 | 2 | 3 | 1 | 2 | 1 | - | 2 | 1 | 3 | 15 |
14 | 2 | 2 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 2 | 3 | 2 | - | 2 | 2 | 15 |
15 | 1 | 2 | 2 | 3 | 1 | 3 | 2 | 2 | 1 | 3 | 3 | 2 | 1 | 2 | - | 2 | 15 |
16 | 2 | 2 | 3 | 2 | 3 | 3 | 1 | 1 | 2 | 0 | 2 | 2 | 3 | 2 | 2 | - | 15 |
If you're only interested in pickleball, stop reading here. If you're interested in algorithms and programming, read on.
Here is the strategy I used to create a schedule with P players on C courts:
To implement this, a player will be an integer; a pair will be an immutable tuple of two players; a game is a list of two pairs; a round is a list of up to C games; and a schedule is a list of rounds.
from collections import Counter
from itertools import combinations
from typing import List, Tuple, Set, Optional
from IPython.core.display import Markdown
import math
import random
Player = int # A player is an integer: e.g., 1, 2, ...
Pair = Tuple[Player, Player] # A pair is a tuple of two players who are partners: (1, 2)
Game = List[Pair] # A game is a list of two pairs of players: [(1, 2), (3, 4)]
Round = List[Game] # A round is a list of games that happen at once: [[(1, 2), (3, 4)], [(5, 6), (7, 8)]]
Schedule = List[Round] # A schedule is a list of rounds that happen one after the other.
We can define all_pairs(P)
, taking care to make the total number of pairs even:
def all_pairs(P: int) -> List[Pair]:
"""All ways in which two out of `P` players can partner."""
players = range(1, P + 1)
pairs = list(combinations(players, 2))
return pairs if len(pairs) % 2 == 0 else [(1, 2), *pairs]
assert all_pairs(4) == [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
assert all_pairs(3) == [(1, 2), (1, 2), (1, 3), (2, 3)] # (1, 2) appears twice, to make the list even
To place pairs into games, we'll choose one pair, pair1
, to play against another pair pair2
, making sure that between the two pairs there are four different players. Then we'll try to make other_games
out of the remaining pairs. If we can't, we'll make a different choice for pair2
.
def games_from_pairs(pairs) -> Optional[List[Game]]:
"Combine pairs of players into a list of games."
if len(pairs) < 2:
return []
pair1 = pairs[0]
for pair2 in pairs:
if len(set(pair1 + pair2)) == 4:
game = [pair1, pair2]
other_games = games_from_pairs(removed(pairs, pair1, pair2))
if other_games is not None:
return [game, *other_games]
return None
def removed(collection, *values) -> list:
"A collection with certain values removed (removed once each)."
result = collection.copy()
for val in values:
result.remove(val)
return result
assert games_from_pairs(all_pairs(4)) == [
[(1, 2), (3, 4)],
[(1, 3), (2, 4)],
[(1, 4), (2, 3)]]
Now we need to take the games and schedule them into rounds such that no player plays twice in any round, and we take as few rounds as possible. We'll define schedule_games(games, C)
to do this using a greedy approach where we start with an empty schedule (with no rounds), and each game is assigned to the first round where it fits, or if it doesn't fit in any existing round, add a new round. This does not guarantee the shortest possible schedule.
def schedule_games(games, C=2) -> Schedule:
"Schedule games onto courts in rounds."
schedule = [] # Start with an empty schedule
for game in games:
find_round(game, schedule, C).append(game)
return schedule
def find_round(game, schedule, C) -> Round:
"""Find a round that can accomodate this game."""
foursome = players(game)
round = first(round for round in schedule if len(round) < C and players(round).isdisjoint(foursome))
if not round: # Add new round to schedule
round = []
schedule.append(round)
return round
def players(x) -> Set[Player]:
"The set of players in a Player, Pair, Game, Round, or Schedule."
return {x} if isinstance(x, Player) else set().union(*map(players, x))
def first(iterable): return next(iter(iterable), None)
Now we have a legal schedule, but we want a good schedule that minimizes the number of rounds and the deviation from playing each opponent twice. The function penalty_points
returns an integer score saying how many penalty points a schedule has: zero penalty for a perfect schedule, length_penalty
penalty for each round over the minimum possible number of rounds, and count_penalties[c]
penalty for each count c
of the number of times two opponents play. This penalty is 0 for opponents who play twice, 1 for opponents who play once or thrice, and higher for bigger deviations from twice.
def penalty_points(sched, P, C, length_penalty=5, count_penalties=[5, 1, 0, 1, 5, 10, 20, 40, 80, 160, 320]):
"""Total penalties for a schedule for P players on C courts."""
shortest = math.ceil(sum(map(len, sched)) / C) # shortest possible schedule
counts = opponent_counts(sched)
return (length_penalty * (len(sched) - shortest) +
sum(count_penalties[counts[pair]] for pair in set(all_pairs(P))))
def opponent_counts(sched) -> Counter:
"A Counter of {(player, opponent): times_played}."
return Counter(canonical((p1, p2))
for round in sched
for A, B in round for p1 in A for p2 in B)
def canonical(pair): "Canonical ordering of pair"; return tuple(sorted(pair))
The final step is to randomly change partners in games until we get a schedule that minimizes penalty points. The function tournament
tries random swaps until it reaches the specified number of tries
or until it achieves a perfect schedule. On each iteration it suggests a random swap, checks if the swap is legal (has 4 distinct players in each game), and then sees if the number of penalty points is reduced. If not, it swaps the players back.
def tournament(P, C=2, tries=200_000, **penalties):
"Schedule games for P players on C courts by randomly swapping game opponents N times."
pairs = all_pairs(P)
games = games_from_pairs(pairs)
sched = schedule_games(games, C)
score = penalty_points(sched, P, C, **penalties)
for _ in range(tries):
if score == 0:
return sched
# Randomly swap pairs from two games
(g1, g2, s1, s2) = idx = *random.sample(range(len(games)), 2), side(), side()
swap(games, idx)
if len(players(games[g1])) == 4 == len(players(games[g2])):
sched2 = schedule_games(games, C)
score2 = penalty_points(sched2, P, C, **penalties)
if score2 <= score:
sched, score = sched2, score2
continue
swap(games, idx) # Swap back if swap did not improve score
return sched
def side() -> int: "Random side of the net"; return random.choice((0, 1))
def swap(games, idx):
"Swap the pair of players at games[g1][s1] with the pair at games[g2][s2]."
(g1, g2, s1, s2) = idx
games[g1][s1], games[g2][s2] = games[g2][s2], games[g1][s1]
Let's see how all of this works:
all_pairs(8)
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8), (6, 7), (6, 8), (7, 8)]
games_from_pairs(_)
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)], [(1, 5), (2, 6)], [(1, 6), (2, 5)], [(1, 7), (2, 8)], [(1, 8), (2, 7)], [(3, 5), (4, 6)], [(3, 6), (4, 5)], [(3, 7), (4, 8)], [(3, 8), (4, 7)], [(5, 6), (7, 8)], [(5, 7), (6, 8)], [(5, 8), (6, 7)]]
schedule_games(_, 2)
[[[(1, 2), (3, 4)], [(5, 6), (7, 8)]], [[(1, 3), (2, 4)], [(5, 7), (6, 8)]], [[(1, 4), (2, 3)], [(5, 8), (6, 7)]], [[(1, 5), (2, 6)], [(3, 7), (4, 8)]], [[(1, 6), (2, 5)], [(3, 8), (4, 7)]], [[(1, 7), (2, 8)], [(3, 5), (4, 6)]], [[(1, 8), (2, 7)], [(3, 6), (4, 5)]]]
sched = tournament(8, 2)
sched
[[[(1, 2), (3, 4)], [(5, 7), (6, 8)]], [[(1, 4), (6, 7)], [(5, 8), (2, 3)]], [[(7, 8), (1, 3)], [(5, 6), (2, 4)]], [[(3, 7), (2, 6)], [(1, 5), (4, 8)]], [[(1, 6), (2, 8)], [(3, 5), (4, 7)]], [[(1, 7), (2, 5)], [(3, 8), (4, 6)]], [[(2, 7), (1, 8)], [(4, 5), (3, 6)]]]
opponent_counts(sched)
Counter({(1, 3): 1, (1, 4): 2, (2, 3): 2, (2, 4): 1, (5, 6): 2, (5, 8): 2, (6, 7): 2, (7, 8): 2, (1, 6): 1, (1, 7): 3, (4, 6): 3, (4, 7): 1, (2, 5): 2, (3, 5): 2, (2, 8): 2, (3, 8): 2, (3, 7): 2, (1, 8): 3, (4, 5): 3, (2, 6): 2, (3, 6): 2, (2, 7): 2, (1, 2): 3, (6, 8): 2, (3, 4): 3, (5, 7): 2, (1, 5): 1, (4, 8): 1})
penalty_points(sched, 8, 2) # 6×(1 penalty point for playing thrice) + 6×(1 for playing once)
12
perfect8 = [
[[(1, 6), (2, 4)], [(3, 5), (7, 8)]],
[[(1, 5), (3, 6)], [(2, 8), (4, 7)]],
[[(2, 3), (6, 8)], [(4, 5), (1, 7)]],
[[(4, 6), (3, 7)], [(1, 2), (5, 8)]],
[[(1, 8), (6, 7)], [(3, 4), (2, 5)]],
[[(2, 6), (5, 7)], [(1, 4), (3, 8)]],
[[(2, 7), (1, 3)], [(4, 8), (5, 6)]],
]
assert penalty_points(perfect8, 8, 2) == 0
I'd like to see the schedule in a neater form, and get statistics on how many times each player plays each other player. The function report(sched)
will do that:
def report(sched) -> str:
"""Return markdown text describing schedule."""
lines = []
out = lines.append
P = len(players(sched))
C = max(map(len, sched))
G = sum(map(len, sched))
out(f'## Schedule for {P} players on {C} courts ({G} games, {len(sched)} rounds)')
schedule_table(sched, C, out)
opponent_table(sched, P, out)
counts = opponent_counts(sched)
cts = Counter(counts[pair] for pair in set(all_pairs(P)))
out('\n<center>Summary of counts:<br>' +
'; '.join(f'{n} {frequency(c)}' for c, n in cts.most_common()) + '</center>')
return '\n'.join(lines)
def frequency(c, words=('never', 'once', 'twice', 'thrice', 'four times')) -> str:
return words[c] if c < len(words) else f'{c}-times'
def schedule_table(sched, C, out: callable):
"""Call `out` on each line of markdown for a schedule table."""
out(header(['Round', *[f'Court {c+1}' for c in range(C)]]))
for r, round in enumerate(sched, 1):
out(row([r, *[f'{a},{b} vs {c},{d}' for (a,b),(c,d) in round]]))
def opponent_table(sched, P, out: callable):
"""Call `out` on each line of markdown for an opponent count table."""
out(header([' ', *range(1, P + 1), 'Total']))
counts = opponent_counts(sched)
for a in range(1, P + 1):
items = ['-' if a == b else counts[canonical((a, b))] for b in range(1, P + 1)]
out(row([f'**{a}**', *items, sum(c for c in items if c != '-') // 2]))
def row(fields) -> str: return '|' + '|'.join(map(str, fields)) + '|'
def header(fields) -> str: return '\n' + row(fields) + '\n' + row(['--'] * len(fields))
Here we see how it works:
print(report(sched))
## Schedule for 8 players on 2 courts (14 games, 7 rounds) |Round|Court 1|Court 2| |--|--|--| |1|1,2 vs 3,4|5,7 vs 6,8| |2|1,4 vs 6,7|5,8 vs 2,3| |3|7,8 vs 1,3|5,6 vs 2,4| |4|3,7 vs 2,6|1,5 vs 4,8| |5|1,6 vs 2,8|3,5 vs 4,7| |6|1,7 vs 2,5|3,8 vs 4,6| |7|2,7 vs 1,8|4,5 vs 3,6| | |1|2|3|4|5|6|7|8|Total| |--|--|--|--|--|--|--|--|--|--| |**1**|-|3|1|2|1|1|3|3|7| |**2**|3|-|2|1|2|2|2|2|7| |**3**|1|2|-|3|2|2|2|2|7| |**4**|2|1|3|-|3|3|1|1|7| |**5**|1|2|2|3|-|2|2|2|7| |**6**|1|2|2|3|2|-|2|2|7| |**7**|3|2|2|1|2|2|-|2|7| |**8**|3|2|2|1|2|2|2|-|7| <center>Summary of counts:<br>16 twice; 6 once; 6 thrice</center>
Markdown(report(sched))
Round | Court 1 | Court 2 |
---|---|---|
1 | 1,2 vs 3,4 | 5,7 vs 6,8 |
2 | 1,4 vs 6,7 | 5,8 vs 2,3 |
3 | 7,8 vs 1,3 | 5,6 vs 2,4 |
4 | 3,7 vs 2,6 | 1,5 vs 4,8 |
5 | 1,6 vs 2,8 | 3,5 vs 4,7 |
6 | 1,7 vs 2,5 | 3,8 vs 4,6 |
7 | 2,7 vs 1,8 | 4,5 vs 3,6 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Total | |
---|---|---|---|---|---|---|---|---|---|
1 | - | 3 | 1 | 2 | 1 | 1 | 3 | 3 | 7 |
2 | 3 | - | 2 | 1 | 2 | 2 | 2 | 2 | 7 |
3 | 1 | 2 | - | 3 | 2 | 2 | 2 | 2 | 7 |
4 | 2 | 1 | 3 | - | 3 | 3 | 1 | 1 | 7 |
5 | 1 | 2 | 2 | 3 | - | 2 | 2 | 2 | 7 |
6 | 1 | 2 | 2 | 3 | 2 | - | 2 | 2 | 7 |
7 | 3 | 2 | 2 | 1 | 2 | 2 | - | 2 | 7 |
8 | 3 | 2 | 2 | 1 | 2 | 2 | 2 | - | 7 |