求32支队伍合法对阵全排列的算法实现方案（附数据）

问题规则 #

• 每对队伍仅赛一场，需生成32支队伍组成16场比赛的所有合法组合，赛程顺序不同视为重复，仅保留一种
• 无需考虑主客场
• 每支队伍仅能与指定的14支对手对阵
• 必须全员配对，未完成全员配对的赛程无效，不纳入结果

允许对阵数据 #

[
  {
    "id": 1,
    "opponents": [8,25,28,2,20,23,19,13,10,4,21,14,32,7]
  },
  {
    "id": 2,
    "opponents": [20,21,32,18,25,28,31,22,23,8,30,11,1,12]
  },
  {
    "id": 3,
    "opponents": [26,6,29,5,24,15,12,23,13,10,9,17,31,22]
  },
  {
    "id": 4,
    "opponents": [14,23,19,8,18,1,31,10,30,11,25,28,26,20]
  },
  {
    "id": 5,
    "opponents": [10,24,9,16,22,6,29,11,26,3,27,7,19,28]
  },
  {
    "id": 6,
    "opponents": [26,3,29,13,10,9,17,14,5,24,15,12,18,27]
  },
  {
    "id": 7,
    "opponents": [16,22,27,5,24,15,12,1,26,13,10,9,17,20]
  },
  {
    "id": 8,
    "opponents": [25,1,28,2,20,23,19,12,9,4,21,14,32,22]
  },
  {
    "id": 9,
    "opponents": [5,10,24,26,3,27,7,31,16,22,6,29,23,8]
  },
  {
    "id": 10,
    "opponents": [5,24,9,26,3,27,7,30,16,22,6,29,4,1]
  },
  {
    "id": 11,
    "opponents": [30,18,31,4,2,20,14,29,21,32,23,19,5,17]
  },
  {
    "id": 12,
    "opponents": [13,17,15,16,22,6,29,2,31,26,3,27,7,8]
  },
  {
    "id": 13,
    "opponents": [17,15,12,26,3,27,7,20,30,16,22,6,29,1]
  },
  {
    "id": 14,
    "opponents": [4,23,19,8,18,1,31,24,30,11,25,28,6,21]
  },
  {
    "id": 15,
    "opponents": [13,17,12,16,22,6,29,21,18,26,3,27,7,25]
  },
  {
    "id": 16,
    "opponents": [22,27,7,13,10,9,17,28,29,5,24,15,12,32]
  },
  {
    "id": 17,
    "opponents": [13,15,12,26,3,27,7,32,11,16,22,6,29,28]
  },
  {
    "id": 18,
    "opponents": [30,11,31,21,32,23,19,6,4,2,20,14,24,15]
  },
  {
    "id": 19,
    "opponents": [4,14,23,30,11,25,28,5,8,18,1,31,29,32]
  },
  {
    "id": 20,
    "opponents": [2,21,32,18,25,28,31,7,4,8,30,11,1,13]
  },
  {
    "id": 21,
    "opponents": [2,20,32,8,30,11,1,27,14,18,25,28,31,15]
  },
  {
    "id": 22,
    "opponents": [16,27,7,13,10,9,17,8,3,5,24,15,12,2]
  },
  {
    "id": 23,
    "opponents": [4,14,19,30,11,25,28,9,8,18,1,31,3,2]
  },
  {
    "id": 24,
    "opponents": [5,10,9,16,22,6,29,18,26,3,27,7,14,25]
  },
  {
    "id": 25,
    "opponents": [8,1,28,4,21,14,32,15,24,2,20,23,19,27]
  },
  {
    "id": 26,
    "opponents": [3,6,29,5,24,15,12,4,13,10,9,17,30,7]
  },
  {
    "id": 27,
    "opponents": [16,22,7,5,24,15,12,25,6,13,10,9,17,21]
  },
  {
    "id": 28,
    "opponents": [8,25,1,4,21,14,32,17,5,2,20,23,19,16]
  },
  {
    "id": 29,
    "opponents": [26,3,6,13,10,9,17,19,5,24,15,12,11,16]
  },
  {
    "id": 30,
    "opponents": [11,18,31,4,2,20,14,26,21,32,23,19,10,13]
  },
  {
    "id": 31,
    "opponents": [30,11,18,21,32,23,19,3,4,2,20,14,9,12]
  },
  {
    "id": 32,
    "opponents": [2,20,21,8,30,11,1,16,19,18,25,28,31,17]
  }
]

算法核心思路 #

这类问题属于完美匹配问题，回溯递归是最直接的实现方式，同时通过剪枝和顺序控制避免重复：

1. 数据预处理：把队伍的允许对阵列表转换成以ID为键的Set结构，实现O(1)时间判断两队是否可配对。
2. 避免重复：每次递归只从当前未配对队伍中取ID最小的作为起始点，仅为它寻找对手，这样不会生成如[1-8,2-3]和[8-1,2-3]这类重复赛程。
3. 回溯递归流程：
   • 维护未配对队伍集合与当前已生成的配对列表。
   • 当未配对集合为空时，将当前配对列表加入结果集。
   • 取出最小ID的未配对队伍，遍历其所有允许对手：
     • 若对手也在未配对集合中，将这对加入当前列表，从集合中移除两者，递归进入下一层。
     • 递归返回后，撤销操作（将队伍加回集合，移除当前配对），尝试下一个对手。

JavaScript实现示例 #

// 预处理数据：将对阵列表转为以ID为键的Set，提升查询速度
function preprocessData(teamsData) {
  const opponentMap = {};
  teamsData.forEach(team => {
    opponentMap[team.id] = new Set(team.opponents);
  });
  return opponentMap;
}

// 递归生成所有合法配对
function generateAllMatchups(opponentMap) {
  const allResults = [];
  // 初始未配对队伍：1-32的Set
  const unpaired = new Set(Array.from({length:32}, (_,i) => i+1));

  // 递归函数
  function backtrack(currentMatchups, remaining) {
    if (remaining.size === 0) {
      // 深拷贝当前配对列表，避免后续修改影响结果
      allResults.push([...currentMatchups]);
      return;
    }

    // 取出当前未配对中ID最小的队伍，避免重复组合
    const currentTeam = Math.min(...remaining);
    remaining.delete(currentTeam);

    // 遍历当前队伍的所有允许对手
    for (const opponent of opponentMap[currentTeam]) {
      if (remaining.has(opponent)) {
        // 生成有序配对（小ID在前），避免重复
        const matchup = currentTeam < opponent ? [currentTeam, opponent] : [opponent, currentTeam];
        currentMatchups.push(matchup);
        remaining.delete(opponent);

        // 递归进入下一层
        backtrack(currentMatchups, remaining);

        // 回溯：撤销操作
        currentMatchups.pop();
        remaining.add(opponent);
      }
    }

    // 回溯：把当前队伍加回未配对集合
    remaining.add(currentTeam);
  }

  backtrack([], unpaired);
  return allResults;
}

// 使用示例
const teamsData = [/* 放入上面的JSON数据 */];
const opponentMap = preprocessData(teamsData);
const allValidMatchups = generateAllMatchups(opponentMap);

// 输出结果数量和第一个组合示例
console.log(`共生成 ${allValidMatchups.length} 组合法赛程`);
console.log("第一组合法赛程示例：", allValidMatchups[0]);

注意事项 #

• 32支队伍的完美匹配组合数量极大，即使有规则限制仍可能生成大量结果，若只需部分结果可在找到指定数量后终止递归。
• 若要提升性能，可提前对对手列表排序，优先尝试剩余可选对手少的队伍配对，减少无效递归分支。

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