生成无重复配对的2v2锦标赛组合算法问题排查

需求说明 #

开发面向2v2模式的锦标赛配对系统，参赛选手总数n为4的倍数，需满足：

• 每名选手仅与其他选手组成配对一次
• 每对选手仅与另一对无重复成员的选手对阵一次
• 总对阵数符合公式：(n-1)*(n/4)（例如4人对应3场、8人对应14场、12人对应33场、16人对应60场）

现有代码问题 #

当前代码能生成所有合法的两人配对，但在组合对阵时未检查两组配对是否存在重复选手，导致输出出现如[["a","b"],["a","c"]]这类包含重复选手的无效对阵，不符合需求。

修复方案 #

核心思路：先生成所有唯一两人配对，再通过回溯法筛选出所有满足条件的对阵组合，同时确保每个配对仅被使用一次。

修复后的代码 #

function generate2v2Matches(players) {
    const n = players.length;
    if (n % 4 !== 0) {
        throw new Error("选手数量必须是4的倍数");
    }

    // 生成所有唯一的两人配对
    const pairs = [];
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            pairs.push([players[i], players[j]]);
        }
    }

    const usedPairs = new Array(pairs.length).fill(false);
    const matches = [];

    // 回溯寻找合法对阵组合
    function backtrack() {
        // 检查是否已生成足够数量的对阵
        if (matches.length === (n - 1) * (n / 4)) {
            return true;
        }

        // 找到第一个未使用的配对作为对阵的第一组
        let firstPairIndex = usedPairs.findIndex(index => !index);
        if (firstPairIndex === -1) return false;

        usedPairs[firstPairIndex] = true;
        const firstPair = pairs[firstPairIndex];
        const firstPairPlayers = new Set(firstPair);

        // 寻找与第一组无重复选手且未被使用的配对作为第二组
        for (let j = firstPairIndex + 1; j < pairs.length; j++) {
            if (usedPairs[j]) continue;

            const secondPair = pairs[j];
            const hasOverlap = secondPair.some(player => firstPairPlayers.has(player));
            if (hasOverlap) continue;

            // 标记第二组为已使用，加入对阵列表
            usedPairs[j] = true;
            matches.push([firstPair, secondPair]);

            // 递归寻找下一组对阵
            if (backtrack()) {
                return true;
            }

            // 回溯：取消标记，移除对阵
            usedPairs[j] = false;
            matches.pop();
        }

        // 回溯：取消第一组的标记
        usedPairs[firstPairIndex] = false;
        return false;
    }

    backtrack();
    return JSON.stringify(matches);
}

// 测试用例
console.log("4人测试：");
console.log(generate2v2Matches(['a', 'b', 'c', 'd']));
// 输出：[[["a","b"],["c","d"]],[["a","c"],["b","d"]],[["a","d"],["b","c"]]]

console.log("\n8人测试（前3场示例）：");
const eightPlayers = ['a','b','c','d','e','f','g','h'];
const eightMatches = JSON.parse(generate2v2Matches(eightPlayers));
console.log(eightMatches.slice(0,3));
// 总对阵数应为14场，符合公式(8-1)*(8/4)=14

代码说明 #

1. 生成所有配对：通过双重循环生成所有不重复的两人组合，确保每个选手两两配对仅一次。
2. 回溯法筛选对阵：
   • 标记已使用的配对，避免重复使用
   • 检查两组配对是否存在重复选手，确保对阵的两队成员完全不重叠
   • 当生成的对阵数量达到公式计算的总数时，终止递归
3. 边界检查：先验证选手数量是否为4的倍数，避免非法输入。

验证结果 #

• 4人场景：生成3场合法对阵，与预期输出一致
• 8人场景：生成14场合法对阵，符合公式计算结果
• 12人/16人场景：可直接运行代码验证，均会生成(n-1)*(n/4)场无重复的合法对阵

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