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

2

5 Answers 5

81

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.

2
  • Why are we fixing 1 fixed and rotating others. Why can't we rotate all? Commented Jan 11, 2023 at 12:39
  • 2
    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. Commented Jan 11, 2023 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

4
  • 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
    Commented May 17, 2020 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
    Commented May 17, 2020 at 21:04
  • 1
    Thanks for saving my ass mate! You algorithm rocks! I tried stackoverflow.com/questions/6648512/… this as well. Totally wrong code!
    – Emu
    Commented Aug 5, 2022 at 16:33
  • Thank you so much! This helped me unstuck myself after so long lol. Thank you!! Commented Aug 13, 2022 at 5: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

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));

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.