UEFA欧冠瑞士赛制赛程分配问询：36队144场赛事分8轮可行性

安全阿岳

2026-6-24

欧冠瑞士赛制赛程编排问题

我已将36支球队编排为包含144场对决的数组，每支球队需对阵8个对手。现需将这些对决划分为8轮，每轮18场比赛，约束条件为每支球队每轮仅能参赛1次，这本质是新版UEFA欧冠瑞士赛制。我尝试用while循环随机打乱对决并重试100次仍未成功，部分轮次的比赛数量不符合要求，请问不修改现有对决的前提下是否可行？

原始尝试代码

const matchups = [
    ["26", "10"], ["26", "23"], ["26", "7"], ["28", "26"], ["21", "26"], ["32", "26"], ["36", "26"], ["26", "22"],
    ["43", "25"], ["25", "54"], ["25", "11"], ["37", "25"], ["16", "25"], ["27", "25"], ["25", "20"], ["25", "2"],
    ["14", "36"], ["37", "36"], ["36", "43"], ["36", "15"], ["11", "36"], ["29", "36"], ["36", "41"],
    ["23", "3"], ["23", "24"], ["23", "43"], ["27", "23"], ["10", "23"], ["29", "23"], ["23", "37"],
    ["54", "13"], ["48", "54"], ["54", "40"], ["54", "41"], ["54", "18"], ["34", "54"], ["12", "54"],
    ["2", "29"], ["2", "12"], ["24", "2"], ["2", "13"], ["7", "2"], ["20", "2"], ["2", "21"],
    ["7", "43"], ["1", "43"], ["43", "15"], ["43", "41"], ["43", "28"],
    ["48", "37"], ["7", "37"], ["22", "37"], ["37", "11"], ["37", "24"],
    ["1", "27"], ["11", "1"], ["1", "12"], ["14", "1"], ["1", "21"], ["9", "1"], ["29", "1"],
    ["35", "16"], ["35", "20"], ["10", "35"], ["28", "35"], ["35", "19"], ["11", "35"], ["22", "35"], ["35", "48"],
    ["15", "33"], ["17", "15"], ["15", "40"], ["15", "10"], ["12", "15"], ["15", "9"],
    ["33", "11"], ["9", "11"], ["11", "34"],
    ["27", "19"], ["48", "27"], ["34", "27"], ["13", "27"], ["27", "33"],
    ["9", "48"], ["9", "17"], ["28", "9"], ["20", "9"], ["14", "9"],
    ["17", "14"], ["28", "17"], ["17", "48"], ["17", "20"], ["16", "17"], ["22", "17"],
    ["19", "3"], ["19", "40"], ["13", "19"], ["19", "22"], ["19", "29"], ["33", "19"],
    ["32", "21"], ["10", "32"], ["18", "32"], ["32", "28"], ["16", "32"], ["32", "3"], ["20", "32"],
    ["22", "28"], ["13", "22"], ["10", "22"],
    ["41", "14"], ["41", "7"], ["41", "29"], ["41", "34"], ["16", "41"],
    ["3", "16"], ["3", "28"], ["3", "10"], ["3", "7"], ["24", "3"],
    ["18", "16"], ["13", "16"],
    ["18", "7"], ["7", "14"],
    ["33", "29"], ["29", "34"],
    ["21", "13"], ["21", "33"], ["21", "12"], ["24", "21"],
    ["20", "48"], ["48", "10"],
    ["40", "14"], ["24", "40"], ["40", "12"], ["40", "18"], ["40", "34"],
    ["12", "18"], ["12", "20"],
    ["34", "13"], ["34", "18"],
    ["14", "24"],
    ["18", "33"], ["33", "24"]
];

const totalRounds = 8;
const matchesEachRound = 18;
let rounds = [];
let trial = 0;

while (trial++ < 100) {
    rounds = Array(totalRounds).fill([]).map(() => []);

    for (const matchup of _.shuffle(matchups)) {
        const findTargetRound = rounds.find(round => 
            round.length < matchesEachRound && _.intersection(round.flat(), matchup).length === 0
        );

        if (findTargetRound) {
            findTargetRound.push(matchup);
        }
    }

    if (rounds.flat().length === matchups.length) {
        break;
    }
}

console.log(rounds);

可行性分析与解决方案

1. 理论可行性

从图论角度看，你的需求等价于将一个8-正则图（每支球队对应一个顶点，每场对决对应一条边，每个顶点度数为8）分解为8个完美匹配（每轮18场比赛恰好覆盖所有36支球队）。根据图论定理：

偶数阶的k-正则图（k≥1）若满足无自环、无重复边，且每个连通分支都是偶数阶，则一定可以分解为k个完美匹配。
你的36支球队是偶数阶，只要对决数组没有重复比赛、没有自环，且每支球队确实有8场对决，那么理论上完全可以完成编排。

2. 原始代码的问题

你采用的随机贪心策略存在明显缺陷：

随机打乱后优先将比赛放入第一个符合条件的轮次，这种短视选择很容易导致后续比赛无法找到合适轮次（比如某支球队的剩余比赛集中在已经满员或冲突的轮次）。
仅尝试100次随机排列，在组合复杂度极高的情况下，成功概率极低。

3. 改进方案：基于图匹配的系统性编排

放弃随机试错，改用逐轮构建完美匹配的方法：

先将对决数组转换为邻接表，记录每支球队的剩余对手。
循环8次，每次为当前轮构建18场无冲突的比赛（完美匹配）：
- 标记所有球队为未匹配状态。
- 遍历未匹配的球队，找到其未匹配的对手，将这场比赛加入当前轮，同时从双方的邻接表中移除该对手（避免重复安排），并标记两队为已匹配。
- 若中途遇到无法匹配的情况，可通过回溯调整选择顺序，或优先安排对手较少的球队（贪心优化）。

改进代码示例

function scheduleRounds(matchups) {
    // 构建邻接表：key为球队ID，value为剩余对手数组
    const adjacency = {};
    matchups.forEach(([a, b]) => {
        if (!adjacency[a]) adjacency[a] = [];
        if (!adjacency[b]) adjacency[b] = [];
        adjacency[a].push(b);
        adjacency[b].push(a);
    });

    const rounds = [];
    const totalRounds = 8;

    for (let r = 0; r < totalRounds; r++) {
        const currentRound = [];
        const matched = new Set();

        // 遍历所有球队，优先处理剩余对手少的球队（贪心优化）
        const teams = Object.keys(adjacency).sort((x, y) => adjacency[x].length - adjacency[y].length);
        
        for (const team of teams) {
            if (matched.has(team)) continue;
            
            // 找到第一个未匹配的对手
            const opponent = adjacency[team].find(opp => !matched.has(opp));
            if (!opponent) throw new Error('无法构建完美匹配，对决数组可能存在问题');
            
            // 添加到当前轮
            currentRound.push([team, opponent]);
            matched.add(team);
            matched.add(opponent);
            
            // 从邻接表中移除双方的这条边
            adjacency[team] = adjacency[team].filter(id => id !== opponent);
            adjacency[opponent] = adjacency[opponent].filter(id => id !== team);
        }

        rounds.push(currentRound);
    }

    return rounds;
}

// 执行编排
try {
    const result = scheduleRounds(matchups);
    console.log('成功生成8轮赛程：');
    result.forEach((round, idx) => {
        console.log(`第${idx+1}轮：`, round);
    });
} catch (e) {
    console.error(e.message);
}

注意事项

先验证对决数组的合法性：确保每支球队恰好有8场比赛，没有重复对决，没有自环。
若改进代码抛出错误，说明你的对决数组可能存在结构问题（比如某支球队的对手数量不对，或图中存在奇数阶的连通分支），需要先修正对决数组。

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