Function to set meetings in a tournament

Question

I have a function getMeetingsPossibilities() that return an array. For example is I have 4 teams it will return ['0-1', '0-2', '0-3', '1-2', '1-3', '2-3'].

I am trying to write a function that would return an array with a set of meetings for n time wanted.

For example getSetsOfMeetings(3) (with 4 teams) would return something like [['0-1','2-3'], ['0-2','1-3'], ['0-3','1-2']]

I can not figure it out how to do this, I tried many time in vain...

I was thinking of something like this :

let meetingsPossibilities = getMeetingsPossibilities(participantsList.length);
//return for 4 teams : ['0-1', '0-2', '0-3', '1-2', '1-3', '2-3']

//Taking out a meeting from meetingPossibilities each time it is used
let oneSetOfMeeting = [];
oneSetOfMeeting.push(meetingPossibilities.splice(randomNumber, 1);

But I can't get the logic to have for each oneSetOfMeeting each teams playing only once. Would you have some idea of a way to do it ?

Answer 1

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:

1. 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.

2. 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.

3. 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.

Answer 2

The kind of tournament in your question is called a "round-robin tournament" - it is a pretty well known form/type of tournament, hence there are already algorithms out there that try to solve your problem.

I just took one of those scheduling algorithms (the circle method) and "translated" it into JS.

The very rough explanation of the circle method is:

You start by pairing the teams up as follows:

1   2    3    4  ...  n/2
n  n-1  n-2  n-3 ... n/2+1

The 1 stays fixed and every other team rotates one position clockwise. So for round 2 the pairings would look like this:

 1    n    2    3  ... n/2-1
n-1  n-2  n-3  n-4 ...  n/2

You do this until you end up where you started and at that point you're gonna have the pairings/meetings for each round.

For further detail (and proof that/why this algorithm works see: https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

Below is the code which I wrote to do exactly what the algorithm I explained above does.

*If you pass an odd number of teams the function will just add 1 team (which is to be treated as the opponent not playing this round) - for example if you have 5 teams, there will be a 6th team in the schedule (whoever plays the 6th team, just doesn't play that round)

function getSchedule(numberOfTeams) {
  if (numberOfTeams % 2 === 1)
    numberOfTeams++;
  const Array1 = [...new Array(numberOfTeams / 2).keys()].map((x) => x + 1);
  const Array2 = [];
  for (let i = numberOfTeams; i > numberOfTeams / 2; i--) {
    Array2.push(i);
  }
  const schedule = [];
  for (let i = 0; i < numberOfTeams - 1; i++) {
  
    // the next two lines can be used interchangeably 
    //(first line has meetings as "1-2, 3-4" - second line has them as [1, 2], [3, 4])
    // just use whatever line serves your purpose best (unit test only works with 2nd line)
    schedule.push(Array1.map((team1, index) => `${team1}-${Array2[index]}`))
    // schedule.push(Array1.map((team1, index) => [team1, Array2[index]]));
    
    Array2.push(Array1.pop() || 0); // the short circuit is only here because I use typescript
    Array1.splice(1, 0, Array2.splice(0, 1)[0]);
  }
  return schedule;
}

console.log(getSchedule(8))
console.log(getSchedule(5))
//yes the 99 is just to show that the function is not that demanding/timecomplex (and could be used to compute large tournaments)
console.log(getSchedule(99))

Since the reuslts you get (especially for larger numbers of teams) are quite difficult/tedious to check for possible errors manually, I wrote a test to do that for me (because I wanted to check if what I wrote actually produces the wanted output). And since I wrote it why not share it with you aswell. So below is the function and additionally the functions unit test

function getSchedule(numberOfTeams) {
  if (numberOfTeams % 2 === 1)
    numberOfTeams++;
  const Array1 = [...new Array(numberOfTeams / 2).keys()].map((x) => x + 1);
  const Array2 = [];
  for (let i = numberOfTeams; i > numberOfTeams / 2; i--) {
    Array2.push(i);
  }
  const schedule = [];
  for (let i = 0; i < numberOfTeams - 1; i++) {

    // the next two lines can be used interchangeably 
    //(first line has meetings as "1-2, 3-4" - second line has them as [1, 2], [3, 4])
    // just use whatever line serves your purpose best (unit test only works with 2nd line)
    // schedule.push(Array1.map((team1, index) => `${team1}-${Array2[index]}`))
    schedule.push(Array1.map((team1, index) => [team1, Array2[index]]));

    Array2.push(Array1.pop() || 0); // the short circuit is only here because I use typescript
    Array1.splice(1, 0, Array2.splice(0, 1)[0]);
  }
  return schedule;
}


//everything below this line is just for testing if we get the desired result (because I can't be bothered to check manually)

function testGetSchedule(schedule) {
  //tests if every round each team only plays once
  if (
    schedule.map(round => new Set(round.flat()).size === round.flat().length).every((x) => x)
  )
    console.log("every team plays only once per round");

  //sorts each meeting (yes array.sort() does not sort numbers as you would expect, but it sorts consistent so it's sufficient)
  const allMeetings = schedule.flat(1);
  allMeetings.forEach((meeting) => meeting.sort());

  //tests if there are any duplicate meetings
  if (new Set(allMeetings.map((meeting) => `${meeting[0]}-${meeting[1]}`)).size === allMeetings.length)
    console.log("no duplicate meetings");
}

testGetSchedule(getSchedule(8))
testGetSchedule(getSchedule(5))
testGetSchedule(getSchedule(99))