JS多循环生成自定义赛程 参赛队超8支时返回结果错误

问题根因 #

原代码用贪心逻辑配对对手：按队伍遍历顺序直接选第一个没在当前比赛日出战的对手配对，没有回溯调整机制。当队伍数是2的幂次（比如8=2³）时，贪心路径刚好能凑齐所有合法对阵；当队伍数是10这类非2的幂次的偶数时，会提前出现死锁：剩下来没配对的队伍，互相都已经在之前的对阵里匹配过了，直接导致赛程生成错误、对阵遗漏或者重复。

问题复现 #

原问题代码如下：

let teams = [
  { id: "Team1" },
  { id: "Team2" },
  { id: "Team3" },
  { id: "Team4" },
  { id: "Team5" },
  { id: "Team6" },
  { id: "Team7" },
  { id: "Team8" },
  {id: "Team9" },
  {id: "Team10" }               
]

// 总轮次
let totRounds = 3
// 存储所有轮次的赛程数组
let rounds = []

for (let i = 0; i < totRounds; i++) {
  // 为每支队伍初始化对手列表，排除自身
  teams.forEach(team => team.enemies = teams.filter(enemy => enemy !== team));
  // 存储主场轮次对阵
  const matches = [];
  // 存储客场轮次对阵（主客场交换）
  const matches_return = [];

  while (teams.some(team => team.enemies.length)) {
    const playing = [];
    const playing_return = []
    for (const team of teams) {
      if (playing.includes(team)) continue;
      const enemy = team.enemies.find(enemy => !playing.includes(enemy));
      if (!enemy) continue;

      // 从双方对手列表中移除已匹配的对阵
      team.enemies.splice(team.enemies.indexOf(enemy), 1);
      enemy.enemies.splice(enemy.enemies.indexOf(team), 1);

      playing.push(team, enemy);
      playing_return.push(enemy, team);
    }

    if (playing.length) matches.push(playing.map(t => t.id))
    if (playing_return.length) matches_return.push(playing_return.map(t => t.id))
  }

  // 合并主客场对阵
  const totalMatches = matches.concat(matches_return)
  rounds.push(totalMatches);
}
console.log(rounds);

上述逻辑在参赛队伍为8支时可正常运行，但队伍数量为10支及以上时运行结果出错，多次调整代码逻辑均未定位到问题根因。

修复后代码 #

直接替换原有逻辑即可，采用标准单循环赛轮转算法生成对阵，支持任意偶数支队伍的赛程生成，不会出现配对死锁：

let teams = [
  { id: "Team1" },
  { id: "Team2" },
  { id: "Team3" },
  { id: "Team4" },
  { id: "Team5" },
  { id: "Team6" },
  { id: "Team7" },
  { id: "Team8" },
  { id: "Team9" },
  { id: "Team10" }               
]

// 总轮次
let totRounds = 3
// 存储所有轮次赛程
let rounds = []

for (let i = 0; i < totRounds; i++) {
  // 浅拷贝当前队伍列表用于轮转，避免修改原数组
  let pool = [...teams]
  // 单循环每队需要打n-1场，对应n-1个比赛日
  const totalMatchDays = pool.length - 1
  const half = pool.length / 2
  const matches = []

  for (let day = 0; day < totalMatchDays; day++) {
    const currentRound = []
    // 取当前轮对阵：第一个对最后一个，第二个对倒数第二个，以此类推
    for (let j = 0; j < half; j++) {
      currentRound.push([pool[j].id, pool[pool.length - 1 - j].id])
    }
    matches.push(...currentRound)
    // 轮转规则：固定第一个元素，其余元素顺时针移动一位
    pool.splice(1, 0, pool.pop())
  }

  // 生成主客场交换的对阵
  const matches_return = matches.map(match => [match[1], match[0]])
  // 合并主客场对阵存入总赛程
  rounds.push(matches.concat(matches_return))
}

console.log(rounds);

修复说明 #

• 采用竞技赛事通用的固定位轮转法生成单循环对阵，时间复杂度低，不存在配对死锁问题，支持任意≥2的偶数支队伍生成赛程
• 每支队伍和其他所有队伍只会对阵一次主客场，不会出现重复对阵、漏对阵的问题
• 如果后续需要支持奇数支队伍参赛，只需要在队伍池里加一个null元素代表轮空，配对到null的队伍当日不安排比赛即可

内容的提问来源于stack exchange，提问作者Damac