ipynb/Pickleball.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\"><i>Peter Norvig<br>Sept 2018<br>Sept 2021</i></div>\n",
    "\n",
    "# Scheduling a Doubles Pickleball Tournament\n",
    "\n",
    "My friend Steve asked for help in creating a schedule for a round-robin rotating-partners doubles [pickleball](https://en.wikipedia.org/wiki/Pickleball) tournament with 8 to 16 players using multiple courts. In this type of tournament:\n",
    "\n",
    "1. A *round* is a set of games played simultaneously on different courts. The fewer the rounds the better. \n",
    "2. No player can be scheduled to play twice in the same round.\n",
    "3. Players change partners from game to game. Each player should partner with every other player exactly once, if possible.\n",
    "4. Each player should play against each opponent player twice, or as close to that as possible.\n",
    "\n",
    "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.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.)\n",
    "\n",
    "## Schedule for 8 players on 2 courts (14 games, 7 rounds)\n",
    "\n",
    "This schedule is perfect in the sense that it meets all the constraints exactly:\n",
    "\n",
    "|Round|Court 1|Court 2|\n",
    "|--|--|--|\n",
    "|1|1,6 vs 2,4|3,5 vs 7,8|\n",
    "|2|1,5 vs 3,6|2,8 vs 4,7|\n",
    "|3|2,3 vs 6,8|4,5 vs 1,7|\n",
    "|4|4,6 vs 3,7|1,2 vs 5,8|\n",
    "|5|1,8 vs 6,7|3,4 vs 2,5|\n",
    "|6|2,6 vs 5,7|1,4 vs 3,8|\n",
    "|7|2,7 vs 1,3|4,8 vs 5,6|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|2|2|2|2|2|2|2|7|\n",
    "|**2**|2|-|2|2|2|2|2|2|7|\n",
    "|**3**|2|2|-|2|2|2|2|2|7|\n",
    "|**4**|2|2|2|-|2|2|2|2|7|\n",
    "|**5**|2|2|2|2|-|2|2|2|7|\n",
    "|**6**|2|2|2|2|2|-|2|2|7|\n",
    "|**7**|2|2|2|2|2|2|-|2|7|\n",
    "|**8**|2|2|2|2|2|2|2|-|7|\n",
    "\n",
    "<center>Summary of counts:<br>28 twice</center>\n",
    "\n",
    "\n",
    "\n",
    "## Schedule for 9 players on 2 courts (18 games, 9 rounds)\n",
    "\n",
    "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\".\n",
    "\n",
    "|Round|Court 1|Court 2|\n",
    "|--|--|--|\n",
    "|1|8,9 vs 1,6|2,4 vs 5,7|\n",
    "|2|6,7 vs 5,9|1,4 vs 3,8|\n",
    "|3|4,7 vs 3,9|2,5 vs 1,8|\n",
    "|4|1,5 vs 7,8|2,9 vs 3,6|\n",
    "|5|6,9 vs 4,5|1,3 vs 2,7|\n",
    "|6|3,7 vs 6,8|4,9 vs 1,2|\n",
    "|7|1,9 vs 3,5|2,6 vs 4,8|\n",
    "|8|1,7 vs 4,6|5,8 vs 2,3|\n",
    "|9|7,9 vs 2,8|5,6 vs 3,4|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|2|2|2|2|1|2|3|2|8|\n",
    "|**2**|2|-|2|2|2|1|2|3|2|8|\n",
    "|**3**|2|2|-|2|2|2|2|2|2|8|\n",
    "|**4**|2|2|2|-|2|3|2|1|2|8|\n",
    "|**5**|2|2|2|2|-|2|2|2|2|8|\n",
    "|**6**|1|1|2|3|2|-|2|2|3|8|\n",
    "|**7**|2|2|2|2|2|2|-|2|2|8|\n",
    "|**8**|3|3|2|1|2|2|2|-|1|8|\n",
    "|**9**|2|2|2|2|2|3|2|1|-|8|\n",
    "\n",
    "<center>Summary of counts:<br>28 twice; 4 thrice; 4 once</center>\n",
    "\n",
    "\n",
    "\n",
    "## Schedule for 10 players on 2 courts (23 games, 12 rounds)\n",
    "\n",
    "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.\n",
    "\n",
    "The following schedule takes the minimum number of rounds and is fairly well-balanced in terms of opponent counts:\n",
    "\n",
    "|Round|Court 1|Court 2|\n",
    "|--|--|--|\n",
    "|1|1,2 vs 3,4|7,9 vs 5,6|\n",
    "|2|2,6 vs 5,8|3,10 vs 4,7|\n",
    "|3|3,8 vs 1,9|4,10 vs 2,5|\n",
    "|4|6,7 vs 1,2|8,9 vs 3,5|\n",
    "|5|1,7 vs 2,8|3,6 vs 5,10|\n",
    "|6|1,6 vs 9,10|7,8 vs 4,5|\n",
    "|7|2,7 vs 3,9|4,8 vs 6,10|\n",
    "|8|1,10 vs 5,7|2,4 vs 6,9|\n",
    "|9|8,10 vs 4,9|1,5 vs 2,3|\n",
    "|10|3,7 vs 6,8|1,4 vs 5,9|\n",
    "|11|2,9 vs 7,10|1,3 vs 4,6|\n",
    "|12|1,8 vs 2,10|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|3|3|2|2|2|2|2|2|2|10|\n",
    "|**2**|3|-|2|2|2|2|3|2|2|2|10|\n",
    "|**3**|3|2|-|2|2|2|2|2|2|1|9|\n",
    "|**4**|2|2|2|-|2|2|1|2|2|3|9|\n",
    "|**5**|2|2|2|2|-|2|2|2|2|2|9|\n",
    "|**6**|2|2|2|2|2|-|2|2|2|2|9|\n",
    "|**7**|2|3|2|1|2|2|-|2|2|2|9|\n",
    "|**8**|2|2|2|2|2|2|2|-|2|2|9|\n",
    "|**9**|2|2|2|2|2|2|2|2|-|2|9|\n",
    "|**10**|2|2|1|3|2|2|2|2|2|-|9|\n",
    "\n",
    "<center>Summary of counts:<br>39 twice; 4 thrice; 2 once</center>\n",
    "\n",
    "\n",
    "## Schedule for 11 players on 2 courts (28 games, 14 rounds)\n",
    "\n",
    "Again, with 11 players, 1 and 2 will play an extra game:\n",
    "\n",
    "|Round|Court 1|Court 2|\n",
    "|--|--|--|\n",
    "|1|1,2 vs 3,11|7,8 vs 6,10|\n",
    "|2|7,10 vs 1,11|6,8 vs 2,4|\n",
    "|3|1,2 vs 9,11|6,7 vs 3,5|\n",
    "|4|1,6 vs 2,3|4,9 vs 5,7|\n",
    "|5|2,9 vs 4,10|3,6 vs 7,11|\n",
    "|6|1,7 vs 2,8|9,10 vs 3,4|\n",
    "|7|8,9 vs 6,11|2,5 vs 3,10|\n",
    "|8|1,10 vs 4,6|5,8 vs 2,7|\n",
    "|9|5,11 vs 6,9|4,8 vs 1,3|\n",
    "|10|1,9 vs 3,7|2,11 vs 4,5|\n",
    "|11|3,9 vs 8,10|5,6 vs 1,4|\n",
    "|12|5,9 vs 1,8|10,11 vs 4,7|\n",
    "|13|1,5 vs 2,10|4,11 vs 3,8|\n",
    "|14|5,10 vs 8,11|7,9 vs 2,6|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|11|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|3|3|2|2|2|2|2|2|2|2|11|\n",
    "|**2**|3|-|2|2|3|2|2|2|2|2|2|11|\n",
    "|**3**|3|2|-|2|1|2|2|2|2|2|2|10|\n",
    "|**4**|2|2|2|-|2|2|1|2|2|3|2|10|\n",
    "|**5**|2|3|1|2|-|2|2|2|2|2|2|10|\n",
    "|**6**|2|2|2|2|2|-|3|2|2|1|2|10|\n",
    "|**7**|2|2|2|1|2|3|-|2|2|2|2|10|\n",
    "|**8**|2|2|2|2|2|2|2|-|2|2|2|10|\n",
    "|**9**|2|2|2|2|2|2|2|2|-|2|2|10|\n",
    "|**10**|2|2|2|3|2|1|2|2|2|-|2|10|\n",
    "|**11**|2|2|2|2|2|2|2|2|2|2|-|10|\n",
    "\n",
    "<center>Summary of counts:<br>47 twice; 5 thrice; 3 once</center>\n",
    "\n",
    "\n",
    "\n",
    "## Schedule for 12 players on 2 courts (33 games, 17 rounds)\n",
    "\n",
    "This schedule is imperfect, but has the minimum number of rounds and is very well balanced:\n",
    "\n",
    "|Round|Court 1|Court 2|\n",
    "|--|--|--|\n",
    "|1|4,12 vs 6,10|2,9 vs 3,11|\n",
    "|2|3,6 vs 1,2|5,10 vs 7,11|\n",
    "|3|3,9 vs 4,8|2,11 vs 5,7|\n",
    "|4|3,5 vs 4,6|1,9 vs 10,12|\n",
    "|5|1,5 vs 8,12|2,7 vs 6,9|\n",
    "|6|7,10 vs 6,8|1,11 vs 4,9|\n",
    "|7|5,9 vs 3,10|7,12 vs 2,4|\n",
    "|8|5,12 vs 3,8|1,7 vs 9,10|\n",
    "|9|1,4 vs 5,6|8,11 vs 9,12|\n",
    "|10|2,8 vs 4,11|3,12 vs 6,7|\n",
    "|11|2,12 vs 4,10|5,11 vs 1,6|\n",
    "|12|1,8 vs 4,7|6,12 vs 9,11|\n",
    "|13|8,9 vs 2,6|3,4 vs 10,11|\n",
    "|14|7,9 vs 4,5|2,3 vs 1,10|\n",
    "|15|2,10 vs 5,8|3,7 vs 11,12|\n",
    "|16|7,8 vs 1,3|\n",
    "|17|1,12 vs 2,5|8,10 vs 6,11|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|11|12|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|2|2|2|3|2|2|2|2|2|1|2|11|\n",
    "|**2**|2|-|2|2|2|2|2|2|2|2|2|2|11|\n",
    "|**3**|2|2|-|2|2|2|2|2|2|2|2|2|11|\n",
    "|**4**|2|2|2|-|2|2|2|2|2|2|2|2|11|\n",
    "|**5**|3|2|2|2|-|2|2|2|1|2|2|2|11|\n",
    "|**6**|2|2|2|2|2|-|2|2|2|2|2|2|11|\n",
    "|**7**|2|2|2|2|2|2|-|2|2|2|2|2|11|\n",
    "|**8**|2|2|2|2|2|2|2|-|2|2|2|2|11|\n",
    "|**9**|2|2|2|2|1|2|2|2|-|2|3|2|11|\n",
    "|**10**|2|2|2|2|2|2|2|2|2|-|2|2|11|\n",
    "|**11**|1|2|2|2|2|2|2|2|3|2|-|2|11|\n",
    "|**12**|2|2|2|2|2|2|2|2|2|2|2|-|11|\n",
    "\n",
    "<center>Summary of counts:<br>62 twice; 2 thrice; 2 once</center>\n",
    "\n",
    "## Schedule for 12 players on 3 courts (33 games, 11 rounds)\n",
    "\n",
    "If 3 courts are available, this schedule takes the minimum number of rounds:\n",
    "\n",
    "\n",
    "|Round|Court 1|Court 2|Court 3|\n",
    "|--|--|--|--|\n",
    "|1|1,2 vs 8,11|5,10 vs 3,4|7,12 vs 6,9|\n",
    "|2|1,6 vs 2,4|5,11 vs 7,10|8,9 vs 3,12|\n",
    "|3|6,8 vs 4,9|2,3 vs 10,12|5,7 vs 1,11|\n",
    "|4|1,5 vs 2,6|3,8 vs 4,7|9,12 vs 10,11|\n",
    "|5|5,9 vs 2,8|3,11 vs 6,10|1,7 vs 4,12|\n",
    "|6|1,8 vs 11,12|3,5 vs 2,7|9,10 vs 4,6|\n",
    "|7|2,10 vs 4,8|3,7 vs 1,9|5,12 vs 6,11|\n",
    "|8|1,10 vs 2,9|8,12 vs 4,5|3,6 vs 7,11|\n",
    "|9|3,9 vs 2,11|5,6 vs 7,8|4,10 vs 1,12|\n",
    "|10|3,10 vs 5,8|9,11 vs 1,4|2,12 vs 6,7|\n",
    "|11|2,5 vs 4,11|1,3 vs 6,12|7,9 vs 8,10|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|11|12|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|3|1|3|1|2|2|1|2|1|3|3|11|\n",
    "|**2**|3|-|2|2|3|2|1|2|2|2|2|1|11|\n",
    "|**3**|1|2|-|1|2|2|3|2|2|3|2|2|11|\n",
    "|**4**|3|2|1|-|2|2|1|3|2|3|1|2|11|\n",
    "|**5**|1|3|2|2|-|2|3|3|0|2|3|1|11|\n",
    "|**6**|2|2|2|2|2|-|3|1|2|1|2|3|11|\n",
    "|**7**|2|1|3|1|3|3|-|2|2|1|2|2|11|\n",
    "|**8**|1|2|2|3|3|1|2|-|3|2|1|2|11|\n",
    "|**9**|2|2|2|2|0|2|2|3|-|3|2|2|11|\n",
    "|**10**|1|2|3|3|2|1|1|2|3|-|2|2|11|\n",
    "|**11**|3|2|2|1|3|2|2|1|2|2|-|2|11|\n",
    "|**12**|3|1|2|2|1|3|2|2|2|2|2|-|11|\n",
    "\n",
    "<center>Summary of counts:<br>35 twice; 16 thrice; 14 once; 1 never</center>\n",
    "\n",
    "## Schedule for 12 players on 3 courts (33 games, 13 rounds)\n",
    "\n",
    "This schedule takes 2 more rounds than minimal, but is much more balanced:\n",
    "\n",
    "|Round|Court 1|Court 2|Court 3|\n",
    "|--|--|--|--|\n",
    "|1|1,2 vs 3,4|5,6 vs 11,12|9,10 vs 7,8|\n",
    "|2|9,11 vs 4,12|8,10 vs 2,6|1,3 vs 5,7|\n",
    "|3|7,12 vs 2,3|5,9 vs 4,6|8,11 vs 1,10|\n",
    "|4|2,4 vs 6,11|5,12 vs 7,10|\n",
    "|5|4,7 vs 2,9|6,12 vs 3,8|\n",
    "|6|1,9 vs 2,10|3,6 vs 7,11|4,5 vs 8,12|\n",
    "|7|5,8 vs 2,12|6,7 vs 4,10|1,11 vs 3,9|\n",
    "|8|1,12 vs 6,9|3,7 vs 4,8|5,10 vs 2,11|\n",
    "|9|2,5 vs 1,6|3,10 vs 4,9|\n",
    "|10|3,11 vs 2,8|1,5 vs 7,9|\n",
    "|11|3,12 vs 10,11|6,8 vs 1,7|\n",
    "|12|3,5 vs 6,10|9,12 vs 2,7|1,8 vs 4,11|\n",
    "|13|5,11 vs 8,9|1,4 vs 10,12|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|11|12|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|2|2|2|2|2|2|2|3|2|2|1|11|\n",
    "|**2**|2|-|2|2|2|2|2|2|2|2|2|2|11|\n",
    "|**3**|2|2|-|2|1|2|3|2|1|2|3|2|11|\n",
    "|**4**|2|2|2|-|1|2|2|2|3|2|2|2|11|\n",
    "|**5**|2|2|1|1|-|3|2|2|2|2|2|3|11|\n",
    "|**6**|2|2|2|2|3|-|2|2|1|2|2|2|11|\n",
    "|**7**|2|2|3|2|2|2|-|2|3|2|0|2|11|\n",
    "|**8**|2|2|2|2|2|2|2|-|1|2|3|2|11|\n",
    "|**9**|3|2|1|3|2|1|3|1|-|2|2|2|11|\n",
    "|**10**|2|2|2|2|2|2|2|2|2|-|2|2|11|\n",
    "|**11**|2|2|3|2|2|2|0|3|2|2|-|2|11|\n",
    "|**12**|1|2|2|2|3|2|2|2|2|2|2|-|11|\n",
    "\n",
    "<center>Summary of counts:<br>51 twice; 8 thrice; 6 once; 1 never</center>\n",
    "\n",
    "\n",
    "## Schedule for 16 players on 4 courts (60 games, 15 rounds)\n",
    "\n",
    "|Round|Court 1|Court 2|Court 3|Court 4|\n",
    "|--|--|--|--|--|\n",
    "|1|1,2 vs 3,4|10,14 vs 7,8|9,13 vs 5,6|11,16 vs 12,15|\n",
    "|2|11,15 vs 2,4|5,7 vs 6,8|9,14 vs 10,13|1,3 vs 12,16|\n",
    "|3|13,16 vs 2,3|4,10 vs 8,15|1,6 vs 11,14|7,12 vs 5,9|\n",
    "|4|10,15 vs 2,6|3,7 vs 11,13|12,14 vs 4,8|1,5 vs 9,16|\n",
    "|5|10,16 vs 2,5|3,8 vs 9,15|6,11 vs 1,14|4,7 vs 12,13|\n",
    "|6|11,12 vs 2,8|3,5 vs 4,6|1,7 vs 9,10|13,14 vs 15,16|\n",
    "|7|1,8 vs 2,7|13,15 vs 4,5|3,6 vs 10,12|9,11 vs 14,16|\n",
    "|8|1,9 vs 2,10|3,11 vs 8,13|4,16 vs 6,12|7,14 vs 5,15|\n",
    "|9|7,13 vs 2,9|5,16 vs 4,11|6,15 vs 3,12|1,10 vs 8,14|\n",
    "|10|5,14 vs 2,12|3,10 vs 4,9|8,16 vs 6,13|1,11 vs 7,15|\n",
    "|11|4,12 vs 2,14|3,15 vs 6,16|1,13 vs 8,9|7,10 vs 5,11|\n",
    "|12|5,8 vs 2,16|3,13 vs 10,11|1,4 vs 6,7|9,12 vs 14,15|\n",
    "|13|7,11 vs 2,15|1,16 vs 4,13|8,12 vs 6,9|5,10 vs 3,14|\n",
    "|14|3,9 vs 2,11|8,10 vs 4,15|6,14 vs 7,16|5,13 vs 1,12|\n",
    "|15|2,13 vs 4,14|3,16 vs 7,9|6,10 vs 1,15|8,11 vs 5,12|\n",
    "\n",
    "\n",
    "||1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|Total|\n",
    "|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|\n",
    "|**1**|-|2|1|2|1|3|3|2|3|3|2|1|2|2|1|2|15|\n",
    "|**2**|2|-|2|3|2|0|2|2|2|2|3|2|2|2|2|2|15|\n",
    "|**3**|1|2|-|2|1|3|1|1|3|3|3|2|3|0|2|3|15|\n",
    "|**4**|2|3|2|-|2|2|1|2|0|2|1|3|3|2|3|2|15|\n",
    "|**5**|1|2|1|2|-|2|3|2|2|2|2|3|2|2|1|3|15|\n",
    "|**6**|3|0|3|2|2|-|2|2|1|2|1|3|1|2|3|3|15|\n",
    "|**7**|3|2|1|1|3|2|-|2|3|2|3|1|2|2|2|1|15|\n",
    "|**8**|2|2|1|2|2|2|2|-|2|3|2|3|2|2|2|1|15|\n",
    "|**9**|3|2|3|0|2|1|3|2|-|3|1|2|3|2|1|2|15|\n",
    "|**10**|3|2|3|2|2|2|2|3|3|-|1|0|1|3|3|0|15|\n",
    "|**11**|2|3|3|1|2|1|3|2|1|1|-|2|2|2|3|2|15|\n",
    "|**12**|1|2|2|3|3|3|1|3|2|0|2|-|1|3|2|2|15|\n",
    "|**13**|2|2|3|3|2|1|2|2|3|1|2|1|-|2|1|3|15|\n",
    "|**14**|2|2|0|2|2|2|2|2|2|3|2|3|2|-|2|2|15|\n",
    "|**15**|1|2|2|3|1|3|2|2|1|3|3|2|1|2|-|2|15|\n",
    "|**16**|2|2|3|2|3|3|1|1|2|0|2|2|3|2|2|-|15|\n",
    "\n",
    "<center>Summary of counts:<br>61 twice; 32 thrice; 22 once; 5 never</center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you're only interested in pickleball,  stop reading here. If you're interested in algorithms and programming,  read on.\n",
    "\n",
    "# Tournament Scheduling Algorithm\n",
    "\n",
    "Here is the strategy I used to create a schedule with *P* players on *C* courts:\n",
    "\n",
    "1. Create a list of player **pairs** in which each pair appears exactly once (except if the length of the list is odd, allow the pair (1, 2) to appear twice).\n",
    "2. Put these pairs together into a list of **games** with no player appearing on both sides of the net in any game.\n",
    "3. Put the games into **rounds** with up to *C* games in a round and no player playing twice in a round.\n",
    "4. Evaluate a **score** for the schedule based on minimizing both the number of rounds and the deviation from playing each opponent twice.\n",
    "5. Repeatedly do the following:\n",
    "  - **Randomly swap** a pair of partners in one game with a pair in another game (such that nobody plays twice in one game).\n",
    "  - Reschedule the games into rounds, and if the score is better, keep the swap; otherwise swap back.\n",
    "  - After a couple hundred thousand random swap attempts, the resulting schedule is usually pretty good.\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from itertools   import combinations\n",
    "from typing      import List, Tuple, Set, Optional\n",
    "from IPython.core.display import Markdown\n",
    "import math\n",
    "import random\n",
    "\n",
    "Player   = int          # A player is an integer: e.g., 1, 2, ...\n",
    "Pair     = Tuple[Player, Player] # A pair is a tuple of two players who are partners: (1, 2)\n",
    "Game     = List[Pair]   # A game is a list of two pairs of players: [(1, 2), (3, 4)]\n",
    "Round    = List[Game]   # A round is a list of games that happen at once: [[(1, 2), (3, 4)], [(5, 6), (7, 8)]]\n",
    "Schedule = List[Round]  # A schedule is a list of rounds that happen one after the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategy Steps 1–3: Pairs, Games, and Rounds\n",
    "\n",
    "We can define `all_pairs(P)`, taking care to make the total number of pairs even:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_pairs(P: int) -> List[Pair]: \n",
    "    \"\"\"All ways in which two out of `P` players can partner.\"\"\"\n",
    "    players = range(1, P + 1)\n",
    "    pairs = list(combinations(players, 2))\n",
    "    return pairs if len(pairs) % 2 == 0 else [(1, 2), *pairs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert all_pairs(4) == [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]\n",
    "assert all_pairs(3) == [(1, 2), (1, 2), (1, 3), (2, 3)] # (1, 2) appears twice, to make the list even"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def games_from_pairs(pairs) -> Optional[List[Game]]:\n",
    "    \"Combine pairs of players into a list of games.\"\n",
    "    if len(pairs) < 2:\n",
    "        return []\n",
    "    pair1 = pairs[0]\n",
    "    for pair2 in pairs:\n",
    "        if len(set(pair1 + pair2)) == 4:\n",
    "            game = [pair1, pair2]\n",
    "            other_games = games_from_pairs(removed(pairs, pair1, pair2))\n",
    "            if other_games is not None:\n",
    "                return [game, *other_games]\n",
    "    return None\n",
    "\n",
    "def removed(collection, *values) -> list:\n",
    "    \"A collection with certain values removed (removed once each).\"\n",
    "    result = collection.copy()\n",
    "    for val in values:\n",
    "        result.remove(val)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert games_from_pairs(all_pairs(4)) == [\n",
    "    [(1, 2), (3, 4)], \n",
    "    [(1, 3), (2, 4)], \n",
    "    [(1, 4), (2, 3)]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def schedule_games(games, C=2) -> Schedule:\n",
    "    \"Schedule games onto courts in rounds.\"\n",
    "    schedule = [] # Start with an empty schedule\n",
    "    for game in games:\n",
    "        find_round(game, schedule, C).append(game)\n",
    "    return schedule\n",
    "\n",
    "def find_round(game, schedule, C) -> Round:\n",
    "    \"\"\"Find a round that can accomodate this game.\"\"\"\n",
    "    foursome = players(game)\n",
    "    round = first(round for round in schedule if len(round) < C and players(round).isdisjoint(foursome))\n",
    "    if not round: # Add new round to schedule\n",
    "        round = []\n",
    "        schedule.append(round)\n",
    "    return round\n",
    "\n",
    "def players(x) -> Set[Player]:\n",
    "    \"The set of players in a Player, Pair, Game, Round, or Schedule.\"\n",
    "    return {x} if isinstance(x, Player) else set().union(*map(players, x))\n",
    "\n",
    "def first(iterable): return next(iter(iterable), None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategy Step 4: Scoring\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def penalty_points(sched, P, C, length_penalty=5, count_penalties=[5, 1, 0, 1, 5, 10, 20, 40, 80, 160, 320]):\n",
    "    \"\"\"Total penalties for a schedule for P players on C courts.\"\"\"\n",
    "    shortest = math.ceil(sum(map(len, sched)) / C) # shortest possible schedule\n",
    "    counts = opponent_counts(sched)\n",
    "    return (length_penalty * (len(sched) - shortest) + \n",
    "            sum(count_penalties[counts[pair]] for pair in set(all_pairs(P))))\n",
    "\n",
    "def opponent_counts(sched) -> Counter:\n",
    "    \"A Counter of {(player, opponent): times_played}.\"\n",
    "    return Counter(canonical((p1, p2)) \n",
    "                   for round in sched\n",
    "                   for A, B in round for p1 in A for p2 in B)\n",
    "\n",
    "def canonical(pair): \"Canonical ordering of pair\"; return tuple(sorted(pair))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategy Step 5: Random Improvement\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tournament(P, C=2, tries=200_000, **penalties):\n",
    "    \"Schedule games for P players on C courts by randomly swapping game opponents N times.\"\n",
    "    pairs = all_pairs(P)\n",
    "    games = games_from_pairs(pairs)\n",
    "    sched = schedule_games(games, C)\n",
    "    score = penalty_points(sched, P, C, **penalties)\n",
    "    for _ in range(tries):\n",
    "        if score == 0:\n",
    "            return sched\n",
    "        # Randomly swap pairs from two games\n",
    "        (g1, g2, s1, s2) = idx = *random.sample(range(len(games)), 2), side(), side()\n",
    "        swap(games, idx)\n",
    "        if len(players(games[g1])) == 4 == len(players(games[g2])):\n",
    "            sched2 = schedule_games(games, C)\n",
    "            score2 = penalty_points(sched2, P, C, **penalties)\n",
    "            if score2 <= score: \n",
    "                sched, score = sched2, score2\n",
    "                continue\n",
    "        swap(games, idx) # Swap back if swap did not improve score\n",
    "    return sched\n",
    "\n",
    "def side() -> int: \"Random side of the net\"; return random.choice((0, 1))\n",
    "\n",
    "def swap(games, idx):\n",
    "    \"Swap the pair of players at games[g1][s1] with the pair at games[g2][s2].\"\n",
    "    (g1, g2, s1, s2) = idx\n",
    "    games[g1][s1], games[g2][s2] = games[g2][s2], games[g1][s1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Working Through Examples\n",
    "\n",
    "Let's see how all of this works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (1, 5),\n",
       " (1, 6),\n",
       " (1, 7),\n",
       " (1, 8),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (2, 5),\n",
       " (2, 6),\n",
       " (2, 7),\n",
       " (2, 8),\n",
       " (3, 4),\n",
       " (3, 5),\n",
       " (3, 6),\n",
       " (3, 7),\n",
       " (3, 8),\n",
       " (4, 5),\n",
       " (4, 6),\n",
       " (4, 7),\n",
       " (4, 8),\n",
       " (5, 6),\n",
       " (5, 7),\n",
       " (5, 8),\n",
       " (6, 7),\n",
       " (6, 8),\n",
       " (7, 8)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_pairs(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(1, 2), (3, 4)],\n",
       " [(1, 3), (2, 4)],\n",
       " [(1, 4), (2, 3)],\n",
       " [(1, 5), (2, 6)],\n",
       " [(1, 6), (2, 5)],\n",
       " [(1, 7), (2, 8)],\n",
       " [(1, 8), (2, 7)],\n",
       " [(3, 5), (4, 6)],\n",
       " [(3, 6), (4, 5)],\n",
       " [(3, 7), (4, 8)],\n",
       " [(3, 8), (4, 7)],\n",
       " [(5, 6), (7, 8)],\n",
       " [(5, 7), (6, 8)],\n",
       " [(5, 8), (6, 7)]]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "games_from_pairs(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[[(1, 2), (3, 4)], [(5, 6), (7, 8)]],\n",
       " [[(1, 3), (2, 4)], [(5, 7), (6, 8)]],\n",
       " [[(1, 4), (2, 3)], [(5, 8), (6, 7)]],\n",
       " [[(1, 5), (2, 6)], [(3, 7), (4, 8)]],\n",
       " [[(1, 6), (2, 5)], [(3, 8), (4, 7)]],\n",
       " [[(1, 7), (2, 8)], [(3, 5), (4, 6)]],\n",
       " [[(1, 8), (2, 7)], [(3, 6), (4, 5)]]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule_games(_, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[[(1, 2), (3, 4)], [(5, 7), (6, 8)]],\n",
       " [[(1, 4), (6, 7)], [(5, 8), (2, 3)]],\n",
       " [[(7, 8), (1, 3)], [(5, 6), (2, 4)]],\n",
       " [[(3, 7), (2, 6)], [(1, 5), (4, 8)]],\n",
       " [[(1, 6), (2, 8)], [(3, 5), (4, 7)]],\n",
       " [[(1, 7), (2, 5)], [(3, 8), (4, 6)]],\n",
       " [[(2, 7), (1, 8)], [(4, 5), (3, 6)]]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sched = tournament(8, 2)\n",
    "sched "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({(1, 3): 1,\n",
       "         (1, 4): 2,\n",
       "         (2, 3): 2,\n",
       "         (2, 4): 1,\n",
       "         (5, 6): 2,\n",
       "         (5, 8): 2,\n",
       "         (6, 7): 2,\n",
       "         (7, 8): 2,\n",
       "         (1, 6): 1,\n",
       "         (1, 7): 3,\n",
       "         (4, 6): 3,\n",
       "         (4, 7): 1,\n",
       "         (2, 5): 2,\n",
       "         (3, 5): 2,\n",
       "         (2, 8): 2,\n",
       "         (3, 8): 2,\n",
       "         (3, 7): 2,\n",
       "         (1, 8): 3,\n",
       "         (4, 5): 3,\n",
       "         (2, 6): 2,\n",
       "         (3, 6): 2,\n",
       "         (2, 7): 2,\n",
       "         (1, 2): 3,\n",
       "         (6, 8): 2,\n",
       "         (3, 4): 3,\n",
       "         (5, 7): 2,\n",
       "         (1, 5): 1,\n",
       "         (4, 8): 1})"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opponent_counts(sched)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "penalty_points(sched, 8, 2) # 6×(1 penalty point for playing thrice) + 6×(1 for playing once)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "perfect8 = [\n",
    " [[(1, 6), (2, 4)], [(3, 5), (7, 8)]],\n",
    " [[(1, 5), (3, 6)], [(2, 8), (4, 7)]],\n",
    " [[(2, 3), (6, 8)], [(4, 5), (1, 7)]],\n",
    " [[(4, 6), (3, 7)], [(1, 2), (5, 8)]],\n",
    " [[(1, 8), (6, 7)], [(3, 4), (2, 5)]],\n",
    " [[(2, 6), (5, 7)], [(1, 4), (3, 8)]],\n",
    " [[(2, 7), (1, 3)], [(4, 8), (5, 6)]], \n",
    "]\n",
    "\n",
    "assert penalty_points(perfect8, 8, 2) == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pretty Markdown Output\n",
    "\n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def report(sched) -> str:\n",
    "    \"\"\"Return markdown text describing schedule.\"\"\"\n",
    "    lines = []\n",
    "    out = lines.append\n",
    "    P = len(players(sched))\n",
    "    C = max(map(len, sched))\n",
    "    G = sum(map(len, sched))\n",
    "    out(f'## Schedule for {P} players on {C} courts ({G} games, {len(sched)} rounds)')\n",
    "    schedule_table(sched, C, out)\n",
    "    opponent_table(sched, P, out)\n",
    "    counts = opponent_counts(sched)\n",
    "    cts = Counter(counts[pair] for pair in set(all_pairs(P)))\n",
    "    out('\\n<center>Summary of counts:<br>' +\n",
    "        '; '.join(f'{n} {frequency(c)}' for c, n in cts.most_common()) + '</center>')\n",
    "    return '\\n'.join(lines)\n",
    "\n",
    "def frequency(c, words=('never', 'once', 'twice', 'thrice', 'four times')) -> str:\n",
    "    return words[c] if c < len(words) else f'{c}-times'\n",
    "\n",
    "def schedule_table(sched, C, out: callable):\n",
    "    \"\"\"Call `out` on each line of markdown for a schedule table.\"\"\"\n",
    "    out(header(['Round', *[f'Court {c+1}' for c in range(C)]]))\n",
    "    for r, round in enumerate(sched, 1):\n",
    "        out(row([r, *[f'{a},{b} vs {c},{d}' for (a,b),(c,d) in round]]))\n",
    "        \n",
    "def opponent_table(sched, P, out: callable):\n",
    "    \"\"\"Call `out` on each line of markdown for an opponent count table.\"\"\"\n",
    "    out(header([' ', *range(1, P + 1), 'Total']))\n",
    "    counts = opponent_counts(sched)\n",
    "    for a in range(1, P + 1):\n",
    "        items = ['-' if a == b else counts[canonical((a, b))] for b in range(1, P + 1)]\n",
    "        out(row([f'**{a}**', *items, sum(c for c in items if c != '-') // 2]))\n",
    "    \n",
    "def row(fields) -> str:    return '|' + '|'.join(map(str, fields)) + '|'\n",
    "def header(fields) -> str: return '\\n' + row(fields) + '\\n' + row(['--'] * len(fields))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see how it works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "## Schedule for 8 players on 2 courts (14 games, 7 rounds)\n",
      "\n",
      "|Round|Court 1|Court 2|\n",
      "|--|--|--|\n",
      "|1|1,2 vs 3,4|5,7 vs 6,8|\n",
      "|2|1,4 vs 6,7|5,8 vs 2,3|\n",
      "|3|7,8 vs 1,3|5,6 vs 2,4|\n",
      "|4|3,7 vs 2,6|1,5 vs 4,8|\n",
      "|5|1,6 vs 2,8|3,5 vs 4,7|\n",
      "|6|1,7 vs 2,5|3,8 vs 4,6|\n",
      "|7|2,7 vs 1,8|4,5 vs 3,6|\n",
      "\n",
      "| |1|2|3|4|5|6|7|8|Total|\n",
      "|--|--|--|--|--|--|--|--|--|--|\n",
      "|**1**|-|3|1|2|1|1|3|3|7|\n",
      "|**2**|3|-|2|1|2|2|2|2|7|\n",
      "|**3**|1|2|-|3|2|2|2|2|7|\n",
      "|**4**|2|1|3|-|3|3|1|1|7|\n",
      "|**5**|1|2|2|3|-|2|2|2|7|\n",
      "|**6**|1|2|2|3|2|-|2|2|7|\n",
      "|**7**|3|2|2|1|2|2|-|2|7|\n",
      "|**8**|3|2|2|1|2|2|2|-|7|\n",
      "\n",
      "<center>Summary of counts:<br>16 twice; 6 once; 6 thrice</center>\n"
     ]
    }
   ],
   "source": [
    "print(report(sched))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "## Schedule for 8 players on 2 courts (14 games, 7 rounds)\n",
       "\n",
       "|Round|Court 1|Court 2|\n",
       "|--|--|--|\n",
       "|1|1,2 vs 3,4|5,7 vs 6,8|\n",
       "|2|1,4 vs 6,7|5,8 vs 2,3|\n",
       "|3|7,8 vs 1,3|5,6 vs 2,4|\n",
       "|4|3,7 vs 2,6|1,5 vs 4,8|\n",
       "|5|1,6 vs 2,8|3,5 vs 4,7|\n",
       "|6|1,7 vs 2,5|3,8 vs 4,6|\n",
       "|7|2,7 vs 1,8|4,5 vs 3,6|\n",
       "\n",
       "| |1|2|3|4|5|6|7|8|Total|\n",
       "|--|--|--|--|--|--|--|--|--|--|\n",
       "|**1**|-|3|1|2|1|1|3|3|7|\n",
       "|**2**|3|-|2|1|2|2|2|2|7|\n",
       "|**3**|1|2|-|3|2|2|2|2|7|\n",
       "|**4**|2|1|3|-|3|3|1|1|7|\n",
       "|**5**|1|2|2|3|-|2|2|2|7|\n",
       "|**6**|1|2|2|3|2|-|2|2|7|\n",
       "|**7**|3|2|2|1|2|2|-|2|7|\n",
       "|**8**|3|2|2|1|2|2|2|-|7|\n",
       "\n",
       "<center>Summary of counts:<br>16 twice; 6 once; 6 thrice</center>"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Markdown(report(sched))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}