Scheduling algorithm for a round-robin tournament?

user_527142 0
Viewed 25369

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

combinatorics algorithm
5 Answers

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

user_31847760

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

user_64257100

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

user_7052960

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
user_45604700
Related