Scheduling algorithm for a round-robin tournament?

Question

I recently did studying stuff and meet up with Donald Knuth. But i didn't found the right algorithm to my problem.

The Problem We have a league with n players. every week they have a match with one other. in n-1 weeks every team fought against each other. there are n/2 matches a day. but one team can only fight once in a week. if we generate an (n/k) combination we get all of the combinations... (assuming k = 2) but i need to bring them in the right order.

My first suggestion was... not the best one. i just made an array, and then let the computer try if he finds the right way. if not, go back to the start, shuffle the array and do it again, well, i programmed it in PHP (n=8) and what comes out works, but take many time, and for n=16 it gives me a timeout as well.

So i thought if maybe we find an algorithm, or anybody knows a book which covers this problem.

And here's my code: http://pastebin.com/Rfm4TquY

Answer 1

The classic algorithm works like this:

Number the teams 1..n. (Here I'll take n=8.)

Write all the teams in two rows.

1 2 3 4
8 7 6 5

The columns show which teams will play in that round (1 vs 8, 2 vs 7, ...).

Now, keep 1 fixed, but rotate all the other teams. In week 2, you get

1 8 2 3
7 6 5 4

and in week 3, you get

1 7 8 2
6 5 4 3

This continues through week n-1, in this case,

1 3 4 5
2 8 7 6

If n is odd, do the same thing but add a dummy team. Whoever is matched against the dummy team gets a bye that week.

Answer 2

Here is the code for it in JavaScript.

function makeRoundRobinPairings(players) {
  if (players.length % 2 == 1) {
    players.push(null);
  }

  const playerCount = players.length;
  const rounds = playerCount - 1;
  const half = playerCount / 2;

  const tournamentPairings = [];

  const playerIndexes = players.map((_, i) => i).slice(1);

  for (let round = 0; round < rounds; round++) {
    const roundPairings = [];

    const newPlayerIndexes = [0].concat(playerIndexes);

    const firstHalf = newPlayerIndexes.slice(0, half);
    const secondHalf = newPlayerIndexes.slice(half, playerCount).reverse();

    for (let i = 0; i < firstHalf.length; i++) {
      roundPairings.push({
        white: players[firstHalf[i]],
        black: players[secondHalf[i]],
      });
    }

    // rotating the array
    playerIndexes.push(playerIndexes.shift());
    tournamentPairings.push(roundPairings);
  }

  return tournamentPairings;
}

UPDATED: Fixed a bug reported in the comments

Answer 3

I made this code, regarding the Okasaki explanation

const roundRobin = (participants) => {
  const tournament = [];

  const half = Math.ceil(participants.length / 2);
  const groupA = participants.slice(0, half);
  const groupB = participants.slice(half, participants.length);
  groupB.reverse();

  tournament.push(getRound(groupA, groupB));


  for(let i=1; i < participants.length - 1; i ++) {
    groupA.splice(1, 0, groupB.shift());
    groupB.push(groupA.pop())
    tournament.push(getRound(groupA, groupB));
  }

  console.log(tournament)
  console.log("Number of Rounds:", tournament.length)
  return tournament;
}

const getRound = (groupA, groupB) => {
  const total = [];
  groupA.forEach((p, i) => {
    total.push([groupA[i], groupB[i]]);
  });
  return total;
}

roundRobin([1,2,3,4,5,6,7])

P.S.: I put an example with an odd amount, so there is a team doesn't play every round, dueling with undefined, you can customize it the way you want

Answer 4

I made an updated solution for this with reusable functions (inspired by varun):

const testData = [
  "Red",
  "Orange",
  "Yellow",
  "Green",
  "Blue",
  "Indigo",
  "Violet",
];

const matchParticipants = (participants) => {
  const p = Array.from(participants);
  if (p % 2 == 1) {
    p.push(null);
  }
  const pairings = [];
  while (p.length != 0) {
    participantA = p.shift();
    participantB = p.pop();
    if (participantA != undefined && participantB != undefined) {
      pairings.push([participantA, participantB]);
    }
  }
  return pairings;
};

const rotateArray = (array) => {
  const p = Array.from(array);
  const firstElement = p.shift();
  const lastElement = p.pop();
  return [firstElement, lastElement, ...p];
};

const generateTournament = (participants) => {
  const tournamentRounds = [];
  const rounds = Math.ceil(participants.length / 2);
  let p = Array.from(participants);
  for (let i = 0; i < rounds; i++) {
    tournamentRounds.push(matchParticipants(p));
    p = rotateArray(p);
  }
  return tournamentRounds;
};

console.log(generateTournament(testData));