Before getting into the solution, a couple of observations:
- With the requirement that each team can only play once per meeting, for
n teams, there is a minimum of n + n % 2 - 1 meetings required. That is to say: for an even number of teams, there will be n - 1 meetings, and for an odd number of teams there will be n meetings (due to the fact one team will be the odd man out and will not be able to play).
- The solution below presents a backtracking approach. Backtracking is essentially a recursive brute force algorithm that incrementally builds a solution, and goes back on its steps if that solution doesn't pan out in subsequent steps. There might be more efficient algorithms available in combinatorics, and I will be happy to read about them here should other users post them.
- I've kept the algorithm simple, but there are additional tweaks and heuristics that could be used to vastly improve performance. As-is, it returns near-instant results for up to 16 teams on my moderately spec'ed laptop. After that, things slow down considerably. I point out a number of possible improvement in the explanation at the end of this answer, but at the end of the day this remains an algorithm with exponential (or at least factorial) time complexity.
Here's the solution:
const schedule = (n) => {
const teams = [...Array(n).keys()];
const games = teams.flatMap(
(t1, i) => teams.slice(i + 1).map((t2) => [t1, t2])
);
const meetings = Array.from(Array(n + n % 2 - 1), () => []);
if (solve(games, meetings, 0, 0)) {
return meetings;
}
throw new Error('No solution found');
}
const solve = (games, meetings, gi, mi) => {
if (gi === games.length) {
return true;
}
if (satisfies(games[gi], meetings[mi])) {
meetings[mi].push(games[gi]);
for (let i = 0; i < meetings.length; i++) {
if (solve(games, meetings, gi + 1, i)) {
return true;
}
}
meetings[mi].pop();
}
return false;
}
const satisfies = (game, meeting) => {
const [t1, t2] = game;
const played = new Set(meeting.flat());
return !played.has(t1) && !played.has(t2);
}
console.log(schedule(4));
For 4 teams, this yields the following results:
[
[ [ 0, 1 ], [ 2, 3 ] ],
[ [ 0, 2 ], [ 1, 3 ] ],
[ [ 0, 3 ], [ 1, 2 ] ]
]
For 8 teams, it looks like this:
[
[ [ 0, 1 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ] ],
[ [ 0, 2 ], [ 1, 3 ], [ 4, 6 ], [ 5, 7 ] ],
[ [ 0, 3 ], [ 1, 2 ], [ 4, 7 ], [ 5, 6 ] ],
[ [ 0, 4 ], [ 1, 5 ], [ 2, 6 ], [ 3, 7 ] ],
[ [ 0, 5 ], [ 1, 4 ], [ 2, 7 ], [ 3, 6 ] ],
[ [ 0, 6 ], [ 1, 7 ], [ 2, 4 ], [ 3, 5 ] ],
[ [ 0, 7 ], [ 1, 6 ], [ 2, 5 ], [ 3, 4 ] ]
]
The implementation itself consists of 3 functions:
satisfies(game, meeting)
This function checks whether a specific game (e.g. team 1 vs. team 2) can still be added to a meeting. This is entirely dependent on whether one or both of teams in question do not already have a game scheduled in that meeting. There are a couple of straightforward improvements that could be made here:
- The maximum number of games per meeting is the quotient of the total number of games divided by the total number of meetings. When deciding whether a game can be added to a meeting, you can skip meetings that are already full.
- The creation of the lookup
Set to determine which teams are already playing in a meeting has a relatively high time-complexity. You can sacrifice some space-complexity instead, and just keep a running track of those sets without recreating them on every invocation.
solve(games, meetings, gi, mi)
This is the function that recursively calls itself to try to assign games to meetings.
- This function first checks the game index (
gi) to see whether there are still games to process; if not, the solution is complete.
- Then, if the conditions described in the previous function are satisfied, it will assign the current game (at the specified index
gi) to the meeting at index mi.
- Subsequently, it will call itself recursively to find a meeting to which the next game can be added. If it fails to find such a meeting, it will backtrack by removing the current game from its allocated meeting. Here, it's important to understand that, due to the nature of the algorithm, it might repeatedly come to a near-solution and then have to backtrack halfway back up the tree to start evaluating the next candidate solution.
schedule(n)
This is the driver function that tries to create a roster for n teams. It prepares arrays of teams, games, and meetings, and then calls the solve() function to allocate the first game to the first meeting, which kicks off the rest of the scheduling process.
