CODEWITHSUNDEEP
algorithmcombinatorics
stkvtflw
stkvtflw

Reputation: 13577

Scheduling algorithm for a tournament with large number of participants?

Say, we have 100+ participants and 3 winning places. I need to schedule as least matches as possible to find 3 winners. The rest of places doesn't matter at all. Round-robin algorithm looks unnecessary expensive.

Here is my solution:

const match = (a, b) => {
  if (!a || !b) {
    return {winner: a || b}
  }
  // simulate match
  const winner = Math.random() > 0.5 ? a : b
  console.log(`Match between ${a} and ${b}: ${winner} wins`)
  return {winner, looser: winner === a ? b : a}
}
let participants = {
  // [id]: {win: Number, loose: Number}
}
let participantsNumber = 100
let n = 0

// create random participants
while(n < participantsNumber) {
  n++
  participants[String(n)] = {win: 0, loose: 0}
}

let round = 0
while(participantsNumber > 3) {
  let odd = true
  let matches = []
  _.map(participants, (winLooseStats, id) => {
    if (odd) {
      odd = false
      matches.push({player_1: id})
    } else {
      odd = true
      let opponentFound = false
      matches.map(match => {
        if (!match.player_2 && !opponentFound) {
          opponentFound = true
          match.player_2 = id
        }
      })
    }
  })
  console.log('matches', matches)
  // run matches
  matches.forEach(({player_1, player_2}) => {
    const {winner, looser} = match(player_1, player_2)
    participants[winner].win++
    if (looser) {
      participants[looser].loose++
    }
  })

  // remove those, who has lost 3 times
  _.map(participants, ({win, loose}, id) => {
    if (loose > 2) {
      console.log(`Player ${id} has lose 3 times`)
      delete participants[id]
      participantsNumber--
    }
  })
  round++
  console.log(`Round ${round} complete. ${participantsNumber} players left`)
}

console.log(`3 champions: ${_.map(participants, (wl, id) => id).join(', ')}`)

JSFIDDLE

~12 rounds per 100 participants. Is it possible to decrease number of rounds?

Upvotes: 0

Views: 230

Answers (1)

Oliver Dain
Oliver Dain

Reputation: 9963

The question is a bit vague, but I think your rules are as follows:

  • Any pair of players plays no more than one match. If A beats B we assume A will always beat B.
  • We assume a transitive property: if A beats B and B beats C the we can assume A beats C and we don't have to schedule a match to find that out.

Assuming that's correct and you have n players then you can solve this optimally using a standard single elimination tournament to find the winner and 2nd place. To find 3rd place you have to add one more match between the two people who didn't make it to the final match.

Upvotes: 0

Related Questions