Creating unique combination of unique pairs-CodePudding

I'm trying to create a tournament system that will pair players together. Each tournament will have multiple of 4 players. Each player will only ever be paired with another player once. Those pairs will only ever play against another pair once. I believe the algorithm is (n-1)*(n/4) where n is the number of players.

Here’s the code:

function generateCombinations(arr) {
  let result = [];

  function combination(start, current) {
    if (current.length === 2) {
      result.push(current);
      return;
    }

    for (let i = start; i < arr.length; i  ) {
      let newCurrent = current.concat(arr[i]);
      if (new Set(newCurrent).size !== newCurrent.length) {
        continue;
      }
      combination(i   1, newCurrent);
    }
  }

  for (let i = 0; i < arr.length; i  ) {
    combination(i   1, [arr[i]]);
  }

  let finalResult = [];
  for (let i = 0; i < result.length; i  = 2) {
    let found = false;
    for (let j = 0; j < finalResult.length; j  ) {
      if (finalResult[j][0][0] === result[i][0] && finalResult[j][0][1] === result[i][1]) {
        found = true;
        break;
      }
    }
    if (!found) {
      finalResult.push([result[i], result[i   1]]);
    }
  }

  return JSON.stringify(finalResult);
}

let elements = ['a', 'b', 'c', 'd'];
let combinations = generateCombinations(elements);
console.log(combinations);

It incorrectly outputs [[["a","b"],["a","c"]],[["a","d"],["b","c"]],[["b","d"],["c","d"]]]It should instead output [[["a","b"],["c","d"]],[["a","c"],["b","d"]],[["a","d"],["b","c"]]]

The difference is that it each each unique pair of pairs should be unique overall. eg. a b will be paired with c d . It’s correctly creating the unique possible pairs, but is incorrectly pairing them with each other.

This code should handle multiples of 4 players up to 16 players.

4 people = 3 rows of 2v2 8 people = 14 rows of 2v2 12 people = 33 rows of 2v2 16 people = 60 rows of 2v2

CodePudding user response：

If I undestand your problem correctly To get the pairs of players, you can divide the players into pairs by looping through the array of players and adding two players at a time to a new array

function getPairs(players) {
  const pairs = [];
  for (let i = 0; i < players.length; i  = 2) {
    pairs.push([players[i], players[i   1]]);
  }
  return pairs;
}

Then you can get the matches to have each pair against another pair

function getMatches(pairs) {
  const matchups = [];
  for (let i = 0; i < pairs.length; i  = 2) {
    matchups.push([pairs[i], pairs[i   1]]);
  }

  return matchups;
}

CodePudding user response：

This is quite interesting. It is rather easy to do with four players, but even six is too hard for my brain, but not for the math people, who have an algorithm for that.

Here is an implementation (buildPairIndexes()), which return tuples of array indexes. Then pairPlayers() just gets the indexes and resolves them for the players.

const players = new Array(6).fill(null).map((_, ix) => String.fromCharCode(97   ix))

function buildPairIndexes(n) {
    if (n % 2 !== 0) {
        throw new Error(`${n} is an odd number`)
    }
    const pairings = []
    const max = n - 1
    for (let i = 0; i < max; i  ) {
        const pairing = [[max, i]]
        for (let k = 1; k < (n / 2); k  ) {
            pairing.push([(i   k) % max, (max   i - k) % max])
        }
        pairings.push(pairing)
    }
    return pairings
}

function pairPlayers(players) {
    const pairings = buildPairIndexes(players.length)
    const pairIxToPlayer = (i) => players[(i   1) % players.length]
    return pairings.map(pairing => pairing.map(pair => pair.map(pairIxToPlayer)))
}
console.log(pairPlayers(players))

For readability, here is the result for six players:

[
  [ [ 'a', 'b' ], [ 'c', 'f' ], [ 'd', 'e' ] ],
  [ [ 'a', 'c' ], [ 'd', 'b' ], [ 'e', 'f' ] ],
  [ [ 'a', 'd' ], [ 'e', 'c' ], [ 'f', 'b' ] ],
  [ [ 'a', 'e' ], [ 'f', 'd' ], [ 'b', 'c' ] ],
  [ [ 'a', 'f' ], [ 'b', 'e' ], [ 'c', 'd' ] ]
]

CodePudding user response：

Here's a simple brute-force solution:

function makeRounds(n) {
    let sets = []
    let rounds = []

    for (let r = 0; r < n - 1; r  ) {
        sets.push({})
        rounds.push([])
    }

    for (let i = 0; i < n - 1; i  ) {
        for (let j = i   1; j < n; j  ) {
            for (let r = 0; r < n - 1; r  ) {
                if (!sets[r][i] && !sets[r][j]) {
                    sets[r][i] = sets[r][j] = 1
                    rounds[r].push([i, j])
                    break
                }
            }
        }
    }

    return rounds
}

for (r of makeRounds(8))
   console.log(r.join(' '))

Basically, for each "round" maintain a set of "teams" (numbers) already in this round. Generate each possible pair [a,b] and put it in the first round whose respective set doesn't contain a or b.