JavaScript tournament scheduling (fixture generation) algorithm

Question

I have just developed a match scheduling algorithm and had to use some pretty funny modular arithmetic. While it works fine i would like to know if my calculations could be simplified any further.

Though it looks a little complicated it's in fact very simple and seems to work very efficiently.

A little bit explanation on my approach;

So for starters, i have 10 teams to match up. Each team will play 9 matches in a fixture such that all teams play with a separate competition at every round.

Accordingly i have an array of team objects as follows;

var teams = [{id: team_0, matches : []}, ... ,{id: team_9, matches: []}]

I would like to show the general layout of the fixture in the table below;

Where mc is the match count, which is 9 in this example. The items with green background are the ones we calculate by iterating over and the red foreground ones are calculated automatically from the iterated ones. Dark green background is the starting index for insertion of the competitors into the matches array.

So for T0 we start with an empty 9 item matches array to be filled with the competitors. However our first competitor will be the last one and then we will continue from the first one like T9 -> T1 -> T2... -> T8. As I have experienced this odd initial ordering results simpler code but i am open to suggestions.

While we are filling the matches array of T0 with a value such as T9 (T0 line first item with dark green background) we also fill same index of the matches array of T9 with T0. (T9 line first item in red)

When we finish T0's matches and come to T1, we already have one item of T1's matches filled while we were calculating the T0 matches. (row T1 column 1, T0 in red) So we start after that one again with T9 and continue with T2 (not T1, since T1 can not play with itself) up until we reach T8. This is where the modulus arithmetic starts showing itself by assigning T8 at index 0.

So this is why I had to come up with some funny modular arithmetic;

• (2*i+j) % mc: Is the calculated index to start inserting results from T9 on.
• (j+mc-i-1) % (mc-i)+i+1: Is the calculated index to pick the competitor from the teams array.

Again i can not make exactly sure if they can be simplified any further but they seem perfectly functional as they are. This is where i need your help.

So the code is;

function fixture(ts){
  var mc = ts.length-1,  // match count is one less than the total number of teams.
      sp = 0,            // calculated start position to insert matches in the matches array.
      tm = 0;            // competing team's calculated index at the input (ts) array.
  return ts.map((t,i,a) => (a.slice(i+1)
                             .forEach(function(_,j,b){
                                        sp = (2*i+j) % mc;
                                        tm = (j+mc-i-1) % (mc-i)+i+1;
                                        t.matches[sp] = a[tm].id;
                                        a[tm].matches[sp] = t.id;
                                      })
                           ,t));
}

var tc = 10,
 teams = Array(tc).fill().map((_,i) => ({id: "Team_"+i, matches: Array(tc-1)}));
result = fixture(teams);
console.log(teams);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Advises to further simplify this code are most welcome.

Answer 1

I have 10 teams to match up. Each team will play 9 matches in a fixture such that all teams play with a separate competition at every round.

Let's build a schedule for 10 teams. I intuitively came up with the following circulant 10x10 matrix A with entry A[i, j] denoting the opponent of team i in round j:

Each row represents the schedule for a single team. We note that for each round j teams are partitioned into pairs playing against each other - i.e. A[A[i, j], j] = i.

However, there is a flaw: According to above schedule, there is a round j for each team where it has to play against itself (the red squares) - i.e. A[i, j] = i.

That's because a correct schedule for 10 teams can only have 9 rounds, not 10. To fix this, we first slice the main diagonal of A - all matches against team 9 - and end up with:

Now, we re-introduce the matches against team 9 wherever a team would have to play against itself (the red squares). We also have to fix the opponents of team 9 to reflect these changes. This practically means that for each round j we swap A[9, j] with A[i, j] where i denotes the self-matched team (the red square):

This is the resulting correct schedule with all swapped matches highlighted in red. This schedule is identical to the one you compute and pretty simple to generate:

1. Create a circulant 10 x 9 matrix where each row is a circular shift of [0,1,2,3,4,5,6,7,8].
2. For each round or column, replace the self-match with a match against team 9 and let team 9 play against the self-matched team.

While there are exactly 945 different ways to partition 10 teams into pairs and thus many more ways to generate a correct schedule, I could not come up with a simpler or more intuitive schedule.

While it works fine i would like to know if my calculations could be simplified any further.

I think that by closely following the above recipe, you can avoid the more obscure arithmetic and come up with a simpler and more intuitive 'generative' algorithm. The scheduling is encapsulated in the round(n, j) function:

// Schedule single round `j` for 'n' teams:
function round(n, j) {
  let m = n - 1;
  let round = Array.from({length: n}, (_, i) => (m + j - i) % m); // circular shift
  round[round[m] = j * (n >> 1) % m] = m; // swapping self-match
  return round;
}

// Schedule matches of 'n' teams:
function fixture(n) {
  let rounds = Array.from({length: n - 1}, (_, j) => round(n, j));
  return Array.from({length: n}, (_, i) => ({
    id: "Team_" + i,
    matches: rounds.map(round => "Team_" + round[i])
  }));
}

// Example:
console.log(fixture(10));