The Problem
Recently I was working on a football league fixture application for a small project and came across an interesting problem - generating a fixture list for any number of teams. How does this look? In each round, which is a group of fixtures containing all (or almost all) of the teams, teams face off against each other. No team can appear twice in the same round, as they more or less take place at the same time. I wanted to include a 'number of meetings' option into the configuration so that each team could face all other teams 1, 2, 3, etc number of times in the course of a single season. Imagine a small 5-a-side league with just a handful of teams. They might want to play each other 6 times in a season to make it last long enough to be interesting. It's also customary to alternate between home and away fixtures where possible. This might not be so relevant for a 5-a-side league where all matches are played at the same venue, but for an 11-a-side league with 20 teams, let's say, it's significant. You don't want to spend every Sunday for 19 weeks travelling to faraway places to play football. I wouldn't, anyway.
By the way, here we're talking about football football, not American football, or handegg as some people call it.
Professional leagues like the Premier League in England and the Bundesliga in Germany have 2 meetings between teams per season, one at home, one away. This adds another constraint to the mixture - the teams should not be playing the same team at home twice or away twice if they only meet twice per season because that would give some teams an advantage. If the meetings is set to 1, there isn't much we can do, but if it's 3, there should be 1 home, 2 away; or 2 home, 1 away. Not 3 home, not 3 away.
Avoiding a team showing up twice in the same round sounds trivial, but when I thought about making these fixtures really random, it threw up some issues. Randomising the fixtures could not be done on the fixture level, only the round level. If I'd randomised on the fixture level, we'd have one teams playing 2 or 3 or theoretically up to all the games in a single round. That simply won't do. We need to give those players a break. Each team can play once in a single round, so randomising simply has to be done on the round level, meaning to shuffle the rounds without any fixtures switching between rounds at the same time.
Round-Robin
I researched a little bit about how the professional leagues actually accomplish this and found that most use the round robin system. The definition of a round-robin is each contestant meets every other participant, usually in turn. This sounded like the sort of thing I was looking for, and the wording there gives a hint about how to implement it.
After reading a bit about the technique, I got it clear in my mind, so now I just needed a way to represent it written down before translating that into code. First I took all the teams and wrote them in a two-row table, reversing the order of the second row. Let's see how that looks with 10 teams.
| A | B | C | D | E |
| J | I | H | G | F |
The first round of fixtures is made up of the first team in the top row versus the first team in the bottom row, and so on. Our first round is therefore:
| A | vs | J |
| B | vs | I |
| C | vs | H |
| D | vs | G |
| E | vs | F |
Now, I just have to shift every team clockwise in the table, so the top row moves one space to the right, the bottom row moves one space to the left and the teams that are pushed off the end move to the same side of the other row, like so:
| J | A | B | C | D |
| I | H | G | F | E |
Team E has fallen off the top row and landed in the right-most side of the bottom row. Team J has been pushed up into the top row to fill the gap left by Team A when it was moved along.
From this we get our second round of fixtures.
| J | vs | I |
| A | vs | H |
| B | vs | G |
| C | vs | F |
| D | vs | E |
Nice! We're definitely getting different fixtures than in the first round, but now comes the first realisation - after 5 rounds are generated, our rows will essentially just be swapped from the first round and we're getting repeat fixtures again while some fixtures like A vs B haven't been added yet. How can we get around this?
Instead of moving all the teams around in the table when we permute them, let's leave one team still and move the others in the same way. Let's use the first team to keep in the same position, since it doesn't actually matter anyway and it'll be easier to keep track of.
Starting again from round 1, let's try the new system.
The first round remains the same, but then after the first permutation, the table now looks like this:
| A | J | B | C | D |
| I | H | G | F | E |
This is very similar to what we had before, except now A remained in the same place and J jumped to the second place in the top row when all the teams got shunted.
Our second round now looks like:
| A | vs | I |
| J | vs | H |
| B | vs | G |
| C | vs | F |
| D | vs | E |
Now we're talking! There won't be any repeat fixtures, all the teams will face each other team exactly once and, as an added bonus, we can repeat this easily to make up multiple meetings. It works for 1 meeting, 2 meetings and any number.
But wait, we're missing an important piece. Which team is the home team and which is the away team. Well, it makes sense for the team on the top row to be home and the team on the bottom to be away, but now we have 9 home fixtures for team A and 4 for all the others, so that won't work. Not only that, but we're not alternating each team between home and away either. Team A won't switch at all anyway, but take Team B as an example. They will have their 4 home fixtures first, followed by 5 away fixtures. That's far from ideal. In fact, it's as far from ideal as we could possibly get!
Instead, what if we just toggled between home and away for the top row? In round 1, the top row is at home, in round 2, the bottom row is at home, in round 3, the top row again is at home and so on and so forth. Our first round has team A at home, the second round has team A away and so on. Pretty simple, and tackles both these issues in one go. Sure, when a team jumps from the top to the bottom they will have 2 games at home or away in a row, and the same when a team jumps from the bottom to the top, but aside from that they will alternate as they are pushed along the top and bottom rows. Pretty neat!
OK, so that's solved it for even numbers of teams, but it breaks down for odd numbers of teams.
As it turns out, we can revert to our original method for odd teams. Let's see it in action. With 9 teams we have:
| A | B | C | D | E |
| I | H | G | F |
We have Team E hanging on the end there, but that's fine. With odd teams, there will always be at least 1 team not included in any round, so that can be the last team in the top row - again we could have chosen the bottom row, it's the same in the end. So, our first round, without Team E:
| A | vs | I |
| B | vs | H |
| C | vs | G |
| D | vs | F |
Now we just rotate all the teams. This way every team will take its turn hanging out on the end of the top row all alone, and they will all meet every other team just once in 9 rounds. Perfect.
The Code
OK, let's try to code this up now. I used TypeScript since this was a Next.js project and I prefer TypeScript over JavaScript for speed of development and nice type safety that eliminates a whole host of potential issues.
I decided to use a class called FixtureGenerator, since this seemed to be a more complex piece of functionality than a function would provide.
I also test-drove the development, since it made keeping track of the implemented functionality much easier and it also helped to increase the speed of development.
I trimmed out some of the tests that I used to test-drive along the way because they don't provide any value after the fact, by testing functionality that is covered elsewhere. Here is the final test suite for brevity.
// fixtureGenerator.test.ts
describe("FixtureGenerator", () => {
describe("with an even number of teams", () => {
describe("with two teams and one meeting", () => {
it("generates just one round with one fixture", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
],
1
).call();
expect(generatedFixtures).toEqual([
{
number: 1,
fixtures: [
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 2, name: "B" },
},
],
},
]);
});
});
describe("with two teams and two meetings", () => {
it("generates two rounds with two fixtures and alternating home and away teams", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
],
2
).call();
expect(generatedFixtures).toEqual([
{
number: 1,
fixtures: [
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 2, name: "B" },
},
],
},
{
number: 2,
fixtures: [
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 1, name: "A" },
},
],
},
]);
});
});
describe("with four teams and one meeting", () => {
it("returns six fixtures with no repeating fixtures, alternating home and away", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
{ id: 3, name: "C" },
{ id: 4, name: "D" },
],
1
).call();
expect(generatedFixtures).toEqual([
{
number: 1,
fixtures: [
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 4, name: "D" },
},
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 3, name: "C" },
},
],
},
{
number: 2,
fixtures: [
{
homeTeam: { id: 3, name: "C" },
awayTeam: { id: 1, name: "A" },
},
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 4, name: "D" },
},
],
},
{
number: 3,
fixtures: [
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 2, name: "B" },
},
{
homeTeam: { id: 3, name: "C" },
awayTeam: { id: 4, name: "D" },
},
],
},
]);
});
});
describe("with 20 teams and two meetings", () => {
it("generates a full season of fixtures", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
{ id: 3, name: "C" },
{ id: 4, name: "D" },
{ id: 5, name: "E" },
{ id: 6, name: "F" },
{ id: 7, name: "G" },
{ id: 8, name: "H" },
{ id: 9, name: "I" },
{ id: 10, name: "J" },
{ id: 11, name: "K" },
{ id: 12, name: "L" },
{ id: 13, name: "M" },
{ id: 14, name: "N" },
{ id: 15, name: "O" },
{ id: 16, name: "P" },
{ id: 17, name: "Q" },
{ id: 18, name: "R" },
{ id: 19, name: "S" },
{ id: 20, name: "T" },
],
2
).call();
expect(generatedFixtures).toHaveLength(38);
const flatFixtures = generatedFixtures.flatMap(round => round.fixtures);
expect(flatFixtures).toHaveLength(380);
const teamBHomeFixtures = flatFixtures.filter(
fixture => fixture.homeTeam.id === 2
);
const teamBAwayFixtures = flatFixtures.filter(
fixture => fixture.awayTeam.id === 2
);
expect(teamBHomeFixtures).toHaveLength(19);
expect(
teamBHomeFixtures.flatMap(fixture => fixture.awayTeam.id)
).toEqual(
expect.arrayContaining([
1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
])
);
expect(teamBAwayFixtures).toHaveLength(19);
expect(
teamBAwayFixtures.flatMap(fixture => fixture.homeTeam.id)
).toEqual(
expect.arrayContaining([
1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
])
);
});
});
});
describe("with an odd number of teams", () => {
describe("with three teams and one meeting", () => {
it("generates three fixtures across three rounds", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
{ id: 3, name: "C" },
],
1
).call();
expect(generatedFixtures[0]).toEqual({
number: 1,
fixtures: [
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 3, name: "C" },
},
],
});
expect(generatedFixtures[1]).toEqual({
number: 2,
fixtures: [
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 3, name: "C" },
},
],
});
expect(generatedFixtures[2]).toEqual({
number: 3,
fixtures: [
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 1, name: "A" },
},
],
});
});
});
describe("with seven teams and one meeting", () => {
it("generates 21 fixtures across seven rounds", () => {
const generatedFixtures = new FixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
{ id: 3, name: "C" },
{ id: 4, name: "D" },
{ id: 5, name: "E" },
{ id: 6, name: "F" },
{ id: 7, name: "G" },
],
1
).call();
expect(generatedFixtures).toHaveLength(7);
expect(generatedFixtures[0].fixtures).toEqual([
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 7, name: "G" },
},
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 6, name: "F" },
},
{
homeTeam: { id: 3, name: "C" },
awayTeam: { id: 5, name: "E" },
},
]);
expect(generatedFixtures[1].fixtures).toEqual([
{
homeTeam: { id: 6, name: "F" },
awayTeam: { id: 7, name: "G" },
},
{
homeTeam: { id: 5, name: "E" },
awayTeam: { id: 1, name: "A" },
},
{
homeTeam: { id: 4, name: "D" },
awayTeam: { id: 2, name: "B" },
},
]);
expect(generatedFixtures[2].fixtures).toEqual([
{
homeTeam: { id: 6, name: "F" },
awayTeam: { id: 5, name: "E" },
},
{
homeTeam: { id: 7, name: "G" },
awayTeam: { id: 4, name: "D" },
},
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 3, name: "C" },
},
]);
expect(generatedFixtures[3].fixtures).toEqual([
{
homeTeam: { id: 4, name: "D" },
awayTeam: { id: 5, name: "E" },
},
{
homeTeam: { id: 3, name: "C" },
awayTeam: { id: 6, name: "F" },
},
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 7, name: "G" },
},
]);
expect(generatedFixtures[4].fixtures).toEqual([
{
homeTeam: { id: 4, name: "D" },
awayTeam: { id: 3, name: "C" },
},
{
homeTeam: { id: 5, name: "E" },
awayTeam: { id: 2, name: "B" },
},
{
homeTeam: { id: 6, name: "F" },
awayTeam: { id: 1, name: "A" },
},
]);
expect(generatedFixtures[5].fixtures).toEqual([
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 3, name: "C" },
},
{
homeTeam: { id: 1, name: "A" },
awayTeam: { id: 4, name: "D" },
},
{
homeTeam: { id: 7, name: "G" },
awayTeam: { id: 5, name: "E" },
},
]);
expect(generatedFixtures[6].fixtures).toEqual([
{
homeTeam: { id: 2, name: "B" },
awayTeam: { id: 1, name: "A" },
},
{
homeTeam: { id: 3, name: "C" },
awayTeam: { id: 7, name: "G" },
},
{
homeTeam: { id: 4, name: "D" },
awayTeam: { id: 6, name: "F" },
},
]);
});
});
});
});And the implementation that satisfies those tests:
// fixtureGenerator.ts
class FixtureGenerator implements TFixtureGenerator {
private topRowHome: Boolean = true;
constructor(
private readonly teams: Team[],
private readonly meetings: number
) {}
call() {
const rounds: ProposedRound[] = [];
let roundNumber = 0;
const roundsPerMeeting = this.teams.length - ((this.teams.length - 1) % 2);
const fixturesPerRound = Math.floor(this.teams.length / 2);
for (
let meetingCounter = 0;
meetingCounter < this.meetings;
meetingCounter++
) {
const [topRow, bottomRow] = this.formTopAndBottomRows();
const startRoundAtHome = meetingCounter % 2 === 0;
this.topRowHome = startRoundAtHome;
for (let round = 0; round < roundsPerMeeting; round++) {
const homeRow = this.topRowHome ? topRow : bottomRow;
const awayRow = this.topRowHome ? bottomRow : topRow;
const fixtures = this.generateRoundFixtures(
homeRow,
awayRow,
fixturesPerRound
);
rounds.push({
number: ++roundNumber,
fixtures,
});
this.rotateTeams(topRow, bottomRow);
}
}
return rounds;
}
private formTopAndBottomRows(): [Team[], Team[]] {
const middle = Math.ceil(this.teams.length / 2);
const topRow = this.teams.slice().splice(0, middle);
const bottomRow = this.teams.slice().splice(middle).reverse();
return [topRow, bottomRow];
}
private generateRoundFixtures(
homeTeams: Team[],
awayTeams: Team[],
fixtureCount: number
): ProposedFixture[] {
let fixtures = [];
for (
let fixtureCounter = 0;
fixtureCounter < fixtureCount;
fixtureCounter++
) {
const homeTeam = homeTeams[fixtureCounter];
const awayTeam = awayTeams[fixtureCounter];
fixtures.push({
homeTeam: homeTeam,
awayTeam: awayTeam,
});
}
return fixtures;
}
private rotateTeams(topRow: Team[], bottomRow: Team[]): void {
this.topRowHome = !this.topRowHome;
const teamToShiftDown = topRow.pop()!;
bottomRow.push(teamToShiftDown);
if (this.teams.length % 2 === 0) {
const teamToLeaveInPlace = topRow.shift()!;
const teamToShiftUp = bottomRow.shift()!;
topRow.unshift(teamToLeaveInPlace, teamToShiftUp);
} else {
const teamToShiftUp = bottomRow.shift()!;
topRow.unshift(teamToShiftUp);
}
}
}The roundsPerMeeting variable looks confusing on first inspection, but it's essentially calculating how many rounds are needed for the all the fixtures to complete a single meeting between all teams. It's the same as the number of teams if the number of teams is odd and the number of teams minus 1 if the number of teams is even.
If it made sense to you first time, hats off to you - it took me a while to write and even longer to simplify.
The table with two rows can be quite simply expressed as two arrays.
I've used a private boolean topRowHome to keep track of which row is home and which is away. This can be kept private since no caller of this class needs to know this detail and it won't be used in tests at all.
I created a private rotateTeams function to perform the permutation of shifting each team round in the table.
From there we have another private function to generate all the fixtures for a single round. When looping through the rounds, we call this function each time and it adds the round into the accumulating rounds array variable, which is modified in place.
We have some types TFixtureGenerator, Team, ProposedFixture and ProposedRound which are omitted here since they are quite simple types and can be deduced easily from the code.
Randomisation
This is all well and good, and if you've followed along so far, you might have already spotted the problem - this isn't random at all!
The terrible thing about this algorithm is that it returns the same results from the same input. Every. Single. Time. This property of an algorithm is called deterministic. If it were a function it would be a pure function. There are no side effects, just predictable output from the input.
Having a deterministic algorithm is great for testing, but not too good for creating a random fixture list, even though that was the whole point.
Right, so what am I doing? This is a failure!
Not quite. I decided, for the sake of TDD and to make it easier to reason about, to make the actual translation from a list of teams into a big list of rounds with fixtures deterministic and create the randomisation elsewhere - in the initial list of teams. Instead of making any changes to the rounds and fixtures once they've been generated, I instead looked to the start of the process and randomly shuffled the teams in the original list. This way, when re-shuffling the list, another random list of fixtures would be generated.
It's definitely not randomness anymore, since the fixtures still follow some kind of pattern, but I figured it would be good enough and, to the human eye, would be more or less undetectable. After running some quick trials, it seemed to me that with 4 teams or fewer, there was only so many permutations possible anyway that any user would realistically not consider the similarities between the fixtures too much. With 5 or more, the sheer number of fixtures becomes too many for anyone to sensibly keep track of when looking through two lists of generated fixtures, therefore it would suffice for this purpose.
Here's how it looks in code. The testing is more difficult, as the randomness makes it much harder to make assertions, although there is still something we can do there.
// randomFixtureGenerator.test.ts
describe("RandomFixtureGenerator", () => {
it("generates fixtures based on a random sorting of the teams", () => {
const generatedFixtures = new RandomFixtureGenerator(
[
{ id: 1, name: "A" },
{ id: 2, name: "B" },
{ id: 3, name: "C" },
{ id: 4, name: "D" },
{ id: 5, name: "E" },
{ id: 6, name: "F" },
{ id: 7, name: "G" },
{ id: 8, name: "H" },
{ id: 9, name: "I" },
{ id: 10, name: "J" },
{ id: 11, name: "K" },
{ id: 12, name: "L" },
{ id: 13, name: "M" },
{ id: 14, name: "N" },
{ id: 15, name: "O" },
{ id: 16, name: "P" },
{ id: 17, name: "Q" },
{ id: 18, name: "R" },
{ id: 19, name: "S" },
{ id: 20, name: "T" },
],
2
).call();
expect(generatedFixtures).toHaveLength(38);
const flatFixtures = generatedFixtures.flatMap(round => round.fixtures);
expect(flatFixtures).toHaveLength(380);
const teamBHomeFixtures = flatFixtures.filter(
fixture => fixture.homeTeam.id === 2
);
const teamBAwayFixtures = flatFixtures.filter(
fixture => fixture.awayTeam.id === 2
);
expect(teamBHomeFixtures).toHaveLength(19);
expect(teamBHomeFixtures.flatMap(fixture => fixture.awayTeam.id)).toEqual(
expect.arrayContaining([
1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
])
);
expect(teamBAwayFixtures).toHaveLength(19);
expect(teamBAwayFixtures.flatMap(fixture => fixture.homeTeam.id)).toEqual(
expect.arrayContaining([
1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
])
);
});
});// randomFixtureGenerator.ts
class RandomFixtureGenerator implements TFixtureGenerator {
constructor(
private readonly teams: Team[],
private readonly meetings: number
) {}
call() {
const randomSortedTeams = randomSortArray<Team>(this.teams);
return new FixtureGenerator(randomSortedTeams, this.meetings).call();
}
}And the randomSortArray tests which is the algorithm doing the shuffling:
// randomSortArray.test.ts
describe("randomSortArray", () => {
it("generates a random array with all the elements of the original array", () => {
const originalArray = ["foo", "bar", "baz", "bat", "hello", "world"];
const randomArray = randomSortArray(originalArray);
expect(randomArray).toHaveLength(originalArray.length);
expect(randomArray).toEqual(expect.arrayContaining(originalArray));
expect(randomArray).not.toEqual([...originalArray]);
});
});Just a single test is needed to verify that the random sorting algorithm, since each result will be different.
Technically, the last expectation, that the result will be different from the original, could well fail, since the algorithm can, on rare occasions, return the same array, but this should be so infrequent that it doesn't cause much concern.
The random sort array implementation is known as the Fisher-Yates shuffle. It just takes every element in the original array, starting with the last, and swaps it randomly with another element.
// randomSortArray.ts
const randomSortArray = <T>(arr: T[]): T[] => {
const newArray = [...arr];
for (let i = newArray.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
const temp = newArray[i];
newArray[i] = newArray[j];
newArray[j] = temp;
}
return newArray;
};My initial idea was to use something simpler like:
arr.sort((a, b) => 0.5 - Math.random());but this has a major drawback that the results are rarely random, as discussed in this article about the Microsoft browser shuffle fail. The Fisher-Yates algorithm is fast and guarantees random results, exactly what I was after.
What is this useful for?
As I expressed in the introduction, this was initially for football fixture generation, but in truth it can be used for pretty much any sports league where 2 teams play each other at a time, optionally alternating between being home or away. My mind even came to the sport (game?) of chess. Home and away can quite easily map to playing with the white and the black pieces respectively. Two players play at any one time and if the tournament format involves every player playing against every other player, then we have a good match.
For sports like rugby, cricket, even handegg American football, baseball, basketball and many others there could also be a use case for such a fixture list generator.
Conclusion
There we have it! 3 relatively simple TypeScript files, each with tests, to generate some random fixtures from a list of teams. If you have questions about any of the code or logic in this post, or want to learn how you can improve your developer skills or find a better job in software, feel free to contact me or directly book a coaching session. Together, we can see how to take your developer career to the next level.