javascript - 随机选择组合，以便每个元素精确地代表两次

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