I'm writing a sports schedule generator. Given T teams (an even number), G games per round (a multiple of T/2), and R rounds I want to generate a schedule matching the criteria:
I have an algorithm that works most of the time, but not always. It is detailed at the end of this question. How can I fix (or replace) this algorithm to robustly work for all reasonable inputs?
This question is similar to Sorting pairs of teams with non-repeating | Round-robin tournament and Algorithm: Selecting pairs of teams from a set of games but has distinct requirements.
For example, assume there are T=4 teams. This gives us 6 possible games:
(T0,T1) (T0,T2) (T0,T3) (T1,T2) (T1,T3) (T2,T3)
If there are G=4 games per round, then the first round must not be this set of games…
(T0,T1) (T0,T2) (T0,T3) (T1,T2)
…because T0 gets to play 3 times, but T3 only gets to play once (a violation of requirement #1). Instead, the first round might look like this, where every team gets to play two games:
(T0,T1) (T2,T3) (T0,T2) (T1,T3)
If that same set of games were repeated for the second round, then the two games (T1,T2) and (T0,T3) would never take place (a violation of requirement #2). So, we want to ensure that they are included in the second round before we pick up new games. A valid schedule for T=4, G=4, R=5 would be:
(T0,T1) (T2,T3) (T0,T2) (T1,T3)
(T0,T3) (T1,T2) (T0,T1) (T2,T3)
(T0,T2) (T1,T3) (T0,T3) (T1,T2)
(T0,T1) (T2,T3) (T0,T2) (T1,T3)
(T0,T3) (T1,T2) (T0,T1) (T2,T3)
As seen, for large values of R it is acceptable for the set of games in a round to be repeated eventually.
The algorithm I have works like so:
currentPool.otherPool.currentPool with the lowest sum when adding together the number of times each team in the game has been seen in this round.currentPool to the otherPool.
currentPool is empty, swap currentPool and otherPool.For many reasonable values of T, G, and R this algorithm works. However, there are some combinations that fail. For example, with T=6, G=3, R=5, it generates this schedule:
(T0,T1) (T2,T3) (T4,T5)
(T0,T2) (T1,T3) (T0,T4)
(T0,T3) (T1,T2) (T0,T5)
(T1,T4) (T2,T5) (T3,T4)
(T1,T5) (T2,T4) (T3,T5)
The first round is correct, but in the second round T0 plays twice and T5 never gets to play. The problem is easy to spot—after picking (T0,T2) and (T1,T3) in round 2 the only game that is possible to satisfy requirement #1 would be (T4,T5), but that game was already used in the first round and per requirement #2 cannot be re-used until all 15 unique games are used up. The algorithm started down a dead-end and had no way to back track.
Finally, for completeness here is a JavaScript version of the algorithm described. Here's sample output of a successful run:
let schedule = singleFieldSchedule({
teams : 8,
maxGamesPerRound : 12,
rounds : 8
})
console.log(schedule.map(round => round.map(game => `(T${game[0]},T${game[1]})`).join(' ')).join('\n') )
(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)
(T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5)
(T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7)
(T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6)
(T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7)
(T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7)
(T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4)
(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)
function singleFieldSchedule({teams=8, maxGamesPerRound=12, rounds=8}={}) {
const uniquePairs = a => a.reduce((res,o1,i,a) => res.concat(a.slice(i+1).map(o2 => [o1,o2])), [])
const teamNames = Array.from(Array(teams).keys())
const fullExposure = uniquePairs(teamNames)
const zeroTeamCounts = teamNames.map(n => [n,0])
// Calculate how many games can be played by each team while keeping things fair
const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
const gamesPerRound = gamesPerTeam * teams/2
const schedule = []
const pools = [fullExposure, []]
let poolIndex = 0
for (let r=0; r<rounds; ++r) {
const round = []
schedule.push(round)
const gamesPerTeam = new Map(zeroTeamCounts)
for (let g=0; g<gamesPerRound; ++g) {
let pool = pools[poolIndex]
if (!pool.length) pool = pools[poolIndex=((poolIndex+1)%2)]
// Find the game whose teams have been seen the least
let bestGameSum = Infinity
let bestGameIndex
for (i=0; i<pool.length; ++i) {
const game = pool[i];
// We square the times seen to favor a game where each team has been seen once
// over a game where one team has been seen twice and the other team has never been seen
const gameSum = gamesPerTeam.get(game[0])**2 + gamesPerTeam.get(game[1])**2
if (gameSum < bestGameSum) {
bestGameSum = gameSum
bestGameIndex = i
}
}
let bestGame = pool.splice(bestGameIndex, 1)[0]
round.push(bestGame)
gamesPerTeam.set(bestGame[0], gamesPerTeam.get(bestGame[0])+1);
gamesPerTeam.set(bestGame[1], gamesPerTeam.get(bestGame[1])+1);
// Put this game into the 'other' pool, to be used once this pool of games is used up
pools[(poolIndex+1) % 2].push(bestGame)
}
// Check to see if any team got screwed this round
const shortedTeams = teamNames.filter(t => gamesPerTeam.get(t)<gamesPerTeam)
shortedTeams.forEach( t => {
const ct = gamesPerTeam.get(t)
console.warn(`Team ${t} only got to play ${ct}/${gamesPerTeam} games in round #${r}`)
})
}
return schedule
}
Lay out a standard round-robin schedule. Then merely take the pairings in order for the quantity of matches you want for each of your rounds.
"The standard schedule" pairs up the teams and rotates all but the first team for each round. For six teams, the schedule looks like this; pairings are adjacent vertically:
0 1 2
5 4 3
0 5 1
4 3 2
0 4 5
3 2 1
0 3 4
2 1 5
0 2 3
1 5 4
There it is: five rounds, each team playing each other team exactly once.
If you have an odd quantity of teams, then designate team 0 as the "bye".
If you need rounds of 6 matches, simply pick them in the order given above, left-to-right in each row:
0-5 1-4 2-3 0-4 5-3 1-2
0-3 4-2 5-1 ... etc.
With 2N teams in the league, the lag between matches is N-1, N, or N+1 matches.