每轮选择成对的球队进行比赛，在重复之前进行最大程度的曝光

Question

我正在编写一个运动时间表生成器。给定 T 支球队（偶数），每轮 G 场比赛（T/2 的倍数), 和 R 回合我想生成符合条件的时间表:

所有球队在一轮中的比赛次数相同。
团队组合在重复之前完全用尽。

我的算法在大多数情况下都有效，但并非总是有效。在这个问题的末尾有详细说明。 我如何修复（或替换）此算法以稳健地处理所有合理的输入？

这个问题与 and Algorithm: Selecting pairs of teams from a set of games类似，但有不同的要求。

例如，假设有 T=4 个团队。这给了我们 6 种可能的游戏：

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)  (T1,T3)  (T2,T3)

如果每轮有G=4局，那么第一轮一定不是这组局...

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)

...因为 T0 可以玩 3 次，而 T3 只能玩一次（违反要求 #1）。相反，第一轮可能看起来像这样，每支球队都可以参加两场比赛：

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)

如果在第二轮重复同样的一组游戏，那么 (T1,T2) 和 (T0,T3) 这两个游戏将永远不会发生（违反要求 #2）。因此，我们要确保在我们选择新游戏之前将它们包含在第二轮中。 T=4、G=4、R=5 的有效时间表是：

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)
(T0,T2)  (T1,T3)  (T0,T3)  (T1,T2)
(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)

可以看出，对于较大的R值，最终重复一轮的游戏集是可以接受的。

我的算法是这样工作的：

计算所有独特的两队组合（可能的比赛）。将此列表另存为 currentPool.
创建一个空列表，命名为 otherPool。
对于每一轮，G次执行以下操作：
- 将本轮比赛中每支球队出现的次数相加，找出总和最小的 currentPool 场比赛。
- 将游戏添加到回合中。
- 将游戏从 currentPool 移动到 otherPool。
  - 如果currentPool为空，交换currentPool和otherPool。

对于 T、G 和 R 的许多合理值，此算法有效。但是，有些组合会失败。例如，T=6，G=3，R=5，它生成这个调度:

(T0,T1)  (T2,T3)  (T4,T5)
(T0,T2)  (T1,T3)  (T0,T4)
(T0,T3)  (T1,T2)  (T0,T5)
(T1,T4)  (T2,T5)  (T3,T4)
(T1,T5)  (T2,T4)  (T3,T5)

第一轮是正确的，但在第二轮中，T0 打了两次，而 T5 永远没有机会打。问题很容易发现——在第 2 轮选择 (T0,T2) 和 (T1,T3) 之后，唯一可能满足要求 #1 的游戏是 (T4,T5)，但该游戏已经在在所有 15 个独特游戏用完之前，第一轮和每个要求 #2 不能重复使用。该算法开始进入死胡同，无法回溯。

最后，为了完整起见，这里是所描述算法的 JavaScript 版本。这是成功运行:

的示例输出

let schedule = singleFieldSchedule({
    teams            : 8,
    maxGamesPerRound : 12,
    rounds           : 8
})
console.log(schedule.map(round => round.map(game => `(T${game[0]},T${game[1]})`).join('  ')).join('\n') )

(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)
(T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5)
(T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7)
(T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6)
(T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7)
(T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7)
(T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4)
(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)

function singleFieldSchedule({teams=8, maxGamesPerRound=12, rounds=8}={}) {
    const uniquePairs = a => a.reduce((res,o1,i,a) => res.concat(a.slice(i+1).map(o2 => [o1,o2])), [])
    const teamNames = Array.from(Array(teams).keys())
    const fullExposure = uniquePairs(teamNames)
    const zeroTeamCounts = teamNames.map(n => [n,0])

    // Calculate how many games can be played by each team while keeping things fair
    const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
    const gamesPerRound = gamesPerTeam * teams/2    

    const schedule = []

    const pools = [fullExposure, []]
    let poolIndex = 0
    for (let r=0; r<rounds; ++r) {
        const round = []
        schedule.push(round)
        const gamesPerTeam = new Map(zeroTeamCounts)
        for (let g=0; g<gamesPerRound; ++g) {
            let pool = pools[poolIndex]
            if (!pool.length) pool = pools[poolIndex=((poolIndex+1)%2)]

            // Find the game whose teams have been seen the least
            let bestGameSum = Infinity
            let bestGameIndex
            for (i=0; i<pool.length; ++i) {
                const game = pool[i];
                // We square the times seen to favor a game where each team has been seen once
                // over a game where one team has been seen twice and the other team has never been seen
                const gameSum = gamesPerTeam.get(game[0])**2 + gamesPerTeam.get(game[1])**2
                if (gameSum < bestGameSum) {
                    bestGameSum = gameSum
                    bestGameIndex = i
                }
            }
            let bestGame = pool.splice(bestGameIndex, 1)[0]
            round.push(bestGame)
            gamesPerTeam.set(bestGame[0], gamesPerTeam.get(bestGame[0])+1);
            gamesPerTeam.set(bestGame[1], gamesPerTeam.get(bestGame[1])+1);

            // Put this game into the 'other' pool, to be used once this pool of games is used up
            pools[(poolIndex+1) % 2].push(bestGame)
        }

        // Check to see if any team got screwed this round
        const shortedTeams = teamNames.filter(t => gamesPerTeam.get(t)<gamesPerTeam)
        shortedTeams.forEach( t => {
            const ct = gamesPerTeam.get(t)
            console.warn(`Team ${t} only got to play ${ct}/${gamesPerTeam} games in round #${r}`)
        })
    }

    return schedule
}

Answer 1

我没有理论上完美的解决方案，但我有一个多项式时间方法应该会更好。

它的核心是最大匹配的 Blossom Algorithm。在每一轮中，使用边缘代表尚未玩过的游戏。这将更有可能找到您当前算法可能失败的简单案例的有效解决方案。特别是你保证球队不能在一轮比赛中打2场比赛，并且尽可能多地使用未使用的比赛。

但是我们可以通过注意我们可以使用 a variation to find maximal weight matchings 来改进这一点。如果您使每条边的权重为 G^i，其中 G 是已玩的游戏数，i 是自上次特定游戏以来的轮数，则团队不能玩 2一轮游戏，我们玩尽可能多的游戏。

本算法保证你的第一个条件，真诚努力做好你的第二个条件。但它并不能保证第二个。（但是，如果您确实有早期重复，它们会很好地分散开来。）

如果你有很多回合，你可以尝试调整权重条件，以确保每个回合平均使用正确的次数。

Answer 2

制定标准的循环赛时间表。然后只需按照您想要的每一轮比赛的数量进行配对。

"The standard schedule" 将团队配对并在每一轮中轮换除第一团队以外的所有团队。对于六支队伍，时间表如下所示；配对垂直相邻：

是这样：五轮比赛，每支球队只与另一支球队交手一次。

如果您的团队数量为奇数，则将团队 0 指定为 "bye"。

如果您需要 6 轮比赛，只需按照上面给出的顺序选择它们，每行从左到右：

0-5  1-4  2-3  0-4  5-3  1-2 
0-3  4-2  5-1  ... etc.

联赛中有 2N 支球队，比赛之间的间隔为 N-1、N 或 N+1 场比赛。

Answer 3

在图形方面，所有团队可能进行的所有游戏的集合是 "complete graph"，即每个团队有一个顶点，每对团队都有边连接的图形。

T=6 和 T=8 的完整图表

找到所有团队只玩一次的游戏对就是找到图的 "perfect matching"：找到接触每个顶点的边，没有一个顶点被多条边接触。

T=6 和 T=8 的完美匹配示例

确保玩完所有可能的游戏——找到一组 "perfect matches" 每条边唯一 select——是 1-factorization of the graph。以下是 T=6 和 T=8 情况的两个不同的 1-因式分解。第一个是手工创建的，而第二个使用接受的答案中描述的循环算法。

鉴于能够为图形生成任何单个 1 分解，问题解决如下：

创建表示团队数量的完整图表的 1 因式分解。
计算单队每轮出场次数N为2*G/T.
对于每一轮，select N 从 1 分解中完美匹配，并使用这些边作为玩该轮的游戏。
- 在随后的回合中，使用后续的完美匹配，以便在第一轮中没有使用的将在以后使用。
- 一旦所有完美匹配都用完，重复select完美匹配的离子。

不需要计算所有 1 因式分解。这样做会提供团队中的球员没有体验过的多样性。例如，上面 T=6 的两个 1 因式分解在 A 队对阵 F 队的情况下显示了不同的完美匹配。然而，当 A 队和 F 队互相比赛时，他们是可能不受 B 队是与 D 队还是 C 队比赛的影响。

此算法的 JavaScript 版本如下：

// Calculate a round-robin schedule using the 'circle' algorithm
// https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm
function roundRobin(teams) {
    const loop = Array.from(Array(teams).keys())
    const rounds = []
    for (let i=0; i<(teams-1); ++i) {
        const round = []
        for (let j=0; j<teams/2; ++j) {
            round.push([loop[j], loop[teams-j-1]].sort())
        }
        loop.splice(1, 0, loop.pop()) // rotate the 'table'
        rounds.push(round)
    }
    return rounds
}

// Play multiple rounds of a round-robin tournament per a single 'round',
// while ensuring that every team plays the same number of games each round,
// and that every team plays every other team as soon as possible.
function multiGameRobin({teams=8, maxGamesPerRound=12, rounds=8}={}) {
    if (teams%2) console.error('number of teams must be even')
    const subrounds = roundRobin(teams)
    const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
    const schedule = []
    for (let r=0; r<rounds; ++r) {
        let round = []
        for (let i=0; i<gamesPerTeam; ++i) {
            round = round.concat(subrounds[(r*gamesPerTeam+i) % subrounds.length])
        }
        schedule[r] = round
    }

    return schedule
}

可能有趣的是——虽然不是原始问题的要求——是在后续轮次中提供完美匹配的不同组合。例如，对于 T=6 有 5 种不同的完美匹配，我们可以称之为 PM1、PM2、PM3、PM4 和 PM5。如果第一轮我们使用PM1、PM2和PM3，那么在第六轮我们可能会使用PM1、PM3和PM5来提供更多的多样性，这样就不会直接重复第一轮的游戏。

每轮选择成对的球队进行比赛，在重复之前进行最大程度的曝光

Selecting pairs of teams to play each round, with maximum exposure before repeats

algorithm

schedule

combinatorics

sports-league-scheduling-problem