我正在编写一个运动时间表生成器。给定T队（偶数）、每轮G场比赛（ T /2 的倍数）和R轮，我想生成一个符合条件的时间表：
- 所有球队在一轮比赛中的比赛数量相同。
- 团队组合在重复之前完全用尽。
我有一个算法在大多数情况下都有效，但并非总是如此。在这个问题的末尾有详细说明。如何修复（或替换）此算法以稳健地适用于所有合理的输入？
这个问题类似于Sorting pair of teams with non-repeating | 循环赛和算法：从一组比赛中选择成对的球队，但有不同的要求。
例如，假设有T =4 个团队。这给了我们 6 种可能的游戏：
(T0,T1) (T0,T2) (T0,T3) (T1,T2) (T1,T3) (T2,T3)
如果每轮有G =4场比赛，那么第一轮一定不是这组比赛……</p>
(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)的游戏是 ，但该游戏已经在第一轮中使用过，并且每个要求 #2 直到全部 15 个才能重新使用独特的游戏用完了。算法从一个死胡同开始，无法回溯。
最后，为了完整起见，这里是所描述算法的 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
}
