28

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

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
Philipp Spiess
  • 3,263
  • 4
  • 26
  • 34
  • 7
    [See Wikipedia](http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm) – Gareth Rees Jul 11 '11 at 10:34
  • 1
    I just add this comment here since this topic seems to be the right place to forward some curious guys to [this related topic at Codereview](https://codereview.stackexchange.com/q/159817/105433). – Redu Feb 06 '20 at 17:19

5 Answers5

78

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.

Wolf
  • 9,679
  • 7
  • 62
  • 108
Chris Okasaki
  • 4,875
  • 1
  • 20
  • 19
  • Why are we fixing 1 fixed and rotating others. Why can't we rotate all? – sam202252012 Jan 11 '23 at 12:39
  • 1
    Try it! Rotate everybody through the rounds beginning with the first configuration above. Pick your favorite number and keep track of who that number is matched with. You'll notice a problem before completing an entire cycle. – Chris Okasaki Jan 11 '23 at 16:19
12

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

varun
  • 300
  • 4
  • 10
  • 1
    Seeing a bug with @varun's code. Using: ['a','b','c','d'] [Round 1] 0: {p1: "a", p2: "c"} 1: {p1: "a", p2: "b"} [Round 2] 0: {p1: "a", p2: "d"} 1: {p1: "b", p2: "c"} [Round 3] 0: {p1: "a", p2: "a"} 1: {p1: "c", p2: "d"} – There May 17 '20 at 20:48
  • 1
    Regarding bug in @varun's code, this fixes it: CHANGE "let playerIndexes = players.slice(1).map((_, i) => i);" TO "let playerIndexes = p.map((_, i) => i); playerIndexes.shift();" – There May 17 '20 at 21:04
  • 1
    Thanks for saving my ass mate! You algorithm rocks! I tried https://stackoverflow.com/questions/6648512/scheduling-algorithm-for-a-round-robin-tournament#answer-72656191 this as well. Totally wrong code! – Emu Aug 05 '22 at 16:33
  • Thank you so much! This helped me unstuck myself after so long lol. Thank you!! – Nirvan Nagar Aug 13 '22 at 05:00
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

Dr.G
  • 448
  • 6
  • 19
1

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));
Joe Sadoski
  • 586
  • 2
  • 7
  • 22
1

here is the code in python for those interested :

def makePairing(inputList):
    if len(inputList) % 2 == 1:
        inputList.append("No Opponent")
    
    pairings = list()
    
    for round in range(len(inputList) - 1):
        round_pairings = list()
        first_half = inputList[:int(len(inputList)/2)]
        second_half = list(reversed(inputList[int(len(inputList)/2):]))

        for element in range(len(first_half)):
            round_pairings.append((first_half[element], second_half[element]))
            
        pairings.append(round_pairings)
        inputList = inputList[0:1] + inputList[2:] + inputList[1:2]
    
    return pairings
Arcyno
  • 4,153
  • 3
  • 34
  • 52