Случайно выбирайте комбинации так, чтобы каждый элемент был представлен ровно дважды

Question

Я пытаюсь выбрать комбинации, чтобы каждый элемент был представлен ровно дважды. В идеале он должен выбирать комбинации случайным образом, чтобы при последующих запусках он не всегда давал одинаковый результат.

Пример набора

[1, 2, 3, 4, 5]

Все возможные комбинации без повторов:

[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4 ], [3, 5], [4, 5]]

Мне нужно получить что-то вроде:

[[1,2], [1,3], [2,5], [3,4], [4,5]]

function comboExists(combos, test) {
  for(let i = 0; i < combos.length; i++){
    if(test[0] === combos[i][0] || test[0] === combos[i][1]) {
      if(test[0] === combos[i][0] && test[1] === combos[i][1]) {
        return true;
      }
      if(test[0] === combos[i][1] && test[1] === combos[i][0]) {
        return true;
      }
    }
  }
  return false;
}

function countPlayerMatches(combos, player) {
  let count = 0;
  for(let i = 0; i < combos.length; i++) {
    if(combos[i][0] === player || combos[i][1] === player) {
      count++;
    }
  }
  return count;
}

function getPlayerPool(combos, players, playerToMatch, maxCount) {
  let playerPool = [];
  if(countPlayerMatches(combos, playerToMatch) < maxCount) {
    for(let i = 0; i < players.length; i++) {
      if(players[i] !== playerToMatch && countPlayerMatches(combos, players[i]) < maxCount) {
        let matchUp = [players[i], playerToMatch];
        if( !comboExists(combos, matchUp)) {
          playerPool.push(players[i]);
        }
      }
    }
  }
  return playerPool;
}

function playersCountLessThanMax(players, combos, maxCount) {
  for(let i = 0; i < players.length; i++){
    if(countPlayerMatches(combos, players[i]) < maxCount) {
      return true;
    }
  }
  return false;
}

function matchPlayers(players, maxCount) {
  let combos = [];
  let tries = 0;
  while(playersCountLessThanMax(players, combos, maxCount)) {
    combos = [];
    tries++;
    for(let i = 0; i < players.length; i++){
      let playerToMatch = players[i];
      if(countPlayerMatches(combos, playerToMatch) < maxCount) {
        let playerPool = getPlayerPool(combos, players, playerToMatch, maxCount);
        if(playerPool.length < 1) {
          break;
        }
        let j = Math.floor((Math.random() * playerPool.length));
        combos.push([playerToMatch, playerPool[j]]);
      }
    }
  }

  console.log(tries);
  return combos;
}

const players = [1, 2, 3, 4, 5];
const maxCount = 2;

console.log(matchPlayers(players, maxCount));

У меня работает код, однако он довольно неэффективен, поскольку он повторяет попытки до правильного решения. Иногда требуется значительное количество попыток, как вы можете видеть ниже.

выход

4 попытки

[[1, 3], [2, 5], [3, 2], [4, 1], [5, 4]]

3 попытки

[[1, 2], [2, 4], [3, 1], [4, 5], [5, 3]]

14 попыток

[[1, 3], [2, 1], [3, 4], [4, 5], [5, 2]]

Answer 1

Вы можете попробовать что-то вроде этого:

Идея:

• Создать функцию, которая возвращает случайное значение из заданных данных.
• Создайте функцию, которая проверяет это значение.
• Создайте карту, чтобы вести подсчет и список значений, которые следует игнорировать.
• При правильном вводе обновите счетчик для этого значения. Постинкрементный, проверьте, достиг ли он порога.
  • Если да, добавьте его к ignoreList.
• При недопустимом вводе перейти к следующему индексу в круговой схеме и повторить приведенное выше доказательство.
• Повторите этот процесс дважды за итерацию, если вам нужна пара из 2 элементов.
• Цикл, пока все элементы не находятся в ignoreList и возврат списка пар

function getRandomPairs(data, maxReps) {
  const map = {};
  let ignoreList = [];
  const result = [];

  function processNumber(ignoreNum) {
    const n = getRandomValue(data, ignoreList.concat(ignoreNum));
    map[n] = (map[n] || 0) + 1;
    if (map[n] >= maxReps) {
      ignoreList.push(n);
    }
    return n;
  }

  while (ignoreList.length !== data.length) {
    const x = processNumber();
    const y = processNumber(x);

    if (result.join(' | ').indexOf([x, y].join()) === -1)
      result.push([x, y]);
    else {
      map[x]--;
      map[y]--;
      ignoreList = ignoreList.filter((n) => ![x,y].includes(n))
    }
  }
  return result;
}

function validateInput(value, ignoreList) {
  return !(Array.isArray(ignoreList) && ignoreList.includes(value))
}

function getRandomIndex(data) {
  return Math.floor(Math.random() * data.length);
}

function getRandomValue(data, ignoreList, index) {
  const i = index !== undefined ? index : getRandomIndex(data);
  const value = data[i];
  if (!validateInput(value, ignoreList)) {
    return getRandomValue(data, ignoreList, (i + 1) % data.length);
  }
  return value;
}

const data = [1, 2, 3, 4, 5];

console.log(getRandomPairs(data, 2).join(' | '));
console.log(getRandomPairs(data, 2).join(' | '));
console.log(getRandomPairs(data, 2).join(' | '));