先抛一个问题8个人打单循环赛每个人要和另外7个人各赛一场场地够用但每人每天最多只能打一场到底几天能打完很多人第一反应是一共28场一天安排4场7天排满。但真正麻烦的从来不是算总天数而是怎么把每天的对阵排出来保证不重不漏。这个就是循环赛日程表问题也是分治法里最经典的教科书案例之一。我最初接触这个问题是在算法课上学分治法当时觉得不就是填个表嘛直到自己动手排才发现8个人的赛程有太多排列方式如果靠脑子硬排排到第5天就开始重复漏人。后来把分治的思路真正吃透才发现这个问题的漂亮之处它不只是教你怎么排比赛而是用构造性思维直接画出一张合法赛程表复杂度还只有O(n²)。这篇文章就把我从理解问题到手写代码、再到被边界条件和各种真实赛制毒打的过程完整捋一遍希望能帮到正在啃算法或者需要实际排赛程的朋友。1. 循环赛日程表问题的本质先搞清楚要排一张什么样的表1.1 一个具体到可以落地的需求描述假设有n个选手参加比赛这里先约定n是2的整数次幂也就是n2, 4, 8, 16……这样。赛制是单循环也就是任意两个选手之间恰好交手一次。每天每个选手最多打一场比赛。问最少需要多少天以及每一天到底让哪几对选手对阵这个最少需要多少天很容易回答每个选手要和另外n-1个选手各打一场每天最多打一场所以每个选手至少需要n-1天。也就是说整个赛程至少持续n-1天。如果能在n-1天内排出一个合法的赛程那就说明这个天数就是最优的不多不少。但排出合法赛程这一件事才是核心难点。什么叫合法具体有三个约束完整性每个选手在n-1天内确实遇到了其余所有n-1个选手。唯一性同一个对手不能在不同天重复出现。对称性如果选手A在第d天和B比赛那么选手B在第d天也必须是和A比赛。这个约束看起来天经地义但在写程序的时候非常容易出错因为我只需要在表里填一个方向另一个方向经常忘了同步。1.2 为什么n-1天是铁律而不是n天这里有个常见的直觉误区。很多人觉得8个人每人要打7场每天打一场所以要7天这个没问题。但也有不少人会想成循环赛是两两配对8个人一轮可以安排4场所有对手组合数是28场所以需要28÷47天。两个角度最后都指向7天但前者的推导才是真正的下界证明因为它基于的是单个选手的参赛场次上限而不是总场次均摊。这个区别在n6时更明显。6个人总场次是15场每轮3场似乎是5天。但同时每个选手也要打5场每天最多打1场所以下界也是5天。但如果是n5呢总场次10场每轮2场需要5轮但每个选手要打4场每天最多一场下界是4天。这两个数不相等说明按总场次均摊算天数并不总是准确的。在n等于偶数时碰巧凑上了在奇数时就会出现轮空。这也是为什么后面要单独聊奇数选手的情况。1.3 用一张矩阵统一表达赛程为了让排赛程这件事可以被程序处理最方便的办法是把赛程表示成一张表格行是选手列是天数第i行第d列填的是第i个选手在第d天的对手编号。比如n4的完整赛程表是这样的选手第1天第2天第3天1234214334124321这张表就满足上面说的三个约束。每一行的数字恰好是1到4除了自己以外的所有编号且不重复每一列四个格子正好组成两对合法的比赛比如第1天是1-2和3-4。有了这个矩阵视角排赛程就变成了填好一张n行n-1列的表格。接下来所有分治的讨论本质上都是围绕高效地填这张表展开。2. 分治思路从哪来把n人切成两组缝合时才见真功夫2.1 先分解上下半区各自为战分治法解决这个问题的第一步非常直觉把n个选手从中间一切分成上半区A和下半区B各n/2人。如果我能先排出n/2个人的内部赛程那我就可以让上下两个半区在比赛的前半段同时打各自内部的小组赛互不干扰。这里的关键是两个半区内部的小组赛用的赛程结构是完全相同的。唯一区别是选手编号不同下半区选手编号比上半区对应位置的选手编号大n/2。也就是说我只需要递归地算出来一个n/2人的赛程表然后把这张表给上半区直接用给下半区用的时候把每个格子里的对手编号加上n/2就行。举个例子n4时上下半区各2人。上半区1和2需要打一场下半区3和4也需要打一场。这两场比赛完全可以在同一天进行第1天安排1-2同时安排3-4。这其实就是把2人的赛程表复制了一份只是把下半区的选手编号整体偏移了2。2.2 合并阶段循环移位配对是核心也是难点内部小组赛解决了上半区之间的比赛但问题还剩一大半上半区的每个选手还要和下半区的每个选手各打一场这部分比赛怎么安排这一段安排需要占用后半段的天数。具体来说前半段上半区和下半区各自打内部赛需要n/2-1天。后半段上半区所有人轮流和下半区所有人打需要n/2天。总天数(n/2-1) n/2 n-1正好对上。后半段的配对方式是整个分治算法最精妙的地方。假设下半区内部编号为1到mmn/2对应真实选手编号为m1到2m。第t个跨组比赛日让上半区的第i个选手去对阵下半区的第j个选手其中j(it-1) mod m也就是让j随着i和t循环移动。用大白话说第一个跨组日上半区1号对阵下半区1号2号对阵下半区2号依次对应第二个跨组日上半区1号对阵下半区2号2号对阵下半区3号最后一个上半区选手回头对阵下半区1号。之后每个跨组日都重复这个整体错位一位的规律。2.3 为什么循环移位不会重也不会漏这个配对规律背后是一个我很喜欢的数学直觉想象两张桌子对面各坐m个人上半区坐一排下半区坐一排。第一场上下对应位置的人交手每打完一天下半区这一排整体往左挪一个座位最后一个人挪到最右边于是每个人第二天都会遇到一个新面孔。重复m天之后每个人恰好和对面每个位置的选手都交手一次。用公式写会更清楚上半区第i个选手在跨组第t天面对的对手是j(it-1) mod m下半区相对编号。固定i让t从1变到mj会取遍1到m的所有值不多不少。这就是一个完整的轮转覆盖数学上可以严格证明完全不依赖运气。到这里分治的三个步骤就齐了分解成上下两个半区递归地解决半区内部赛程再通过循环移位把两个半区缝合起来。整个算法的正确性可以用数学归纳法证明如果n/2人的赛程是合法的那么按上述方式拼接出的n人赛程也一定是合法的。3. 递归实现与逐轮验证写能跑的代码而不是只背伪代码3.1 一份可以直接跑的C实现理解了原理之后写代码其实非常直接。这里给出一份我习惯用的递归版本数据结构就是上一节说的矩阵行表示选手列表示天数格子内容是对手编号。#include iostream #include vector using namespace std; // 生成 n 个选手的单循环赛程n 必须是 2 的幂且 n 2 // 返回矩阵 ansans[i][d] 表示第 i1 个选手在第 d 天的对手编号 vectorvectorint schedule(int n) { if (n 2) { // 两个人只需要打一天 return {{2}, {1}}; } int m n / 2; auto inner schedule(m); // 递归生成 m 人赛程 vectorvectorint ans(n, vectorint(n - 1)); int innerDays m - 1; // 前 innerDays 天打半区内战 // 上半区直接用内层赛程下半区把对手编号整体偏移 m for (int i 0; i m; i) { for (int d 0; d innerDays; d) { ans[i][d] inner[i][d]; // 上半区 1..m ans[i m][d] inner[i][d] m; // 下半区 m1..2m } } // 后 m 天打跨组对抗使用循环移位配对 for (int t 0; t m; t) { int day innerDays t; for (int i 0; i m; i) { int j (i t) % m; // 下半区相对编号 ans[i][day] j m 1; // 上半区第 i1 号 vs 下半区第 jm1 号 ans[j m][day] i 1; // 对称方向必须同步填写 } } return ans; }这个实现有个细节值得注意我在外层用0-based下标访问矩阵但格子里的选手编号是1-based。也就是ans[i][d]里的第i1个选手内部编号是i1。很多初学者在这里混导致返回的矩阵第一行全是0或者出现自己打自己的情况。3.2 手推n4把递归过程摊开看代码写出来是一回事能徒手推一遍才算真懂。我们来看n4的时候发生了什么。先递归到n2得到inner为[[2], [1]]也就是选手1第1天对选手2选手2第1天对选手1。回到n4时m2innerDays1。前1天上半区选手1和2直接复制inner所以第1天是1-2下半区选手3和4的对手分别是inner[0][0]24和inner[1][0]23所以第1天同时进行3-4。这一天没问题。后2天是跨组对抗t从0到1。t0day1i0时j0所以选手1第2天对阵j213选手3第2天对阵i11。i1时j1选手2第2天对阵4选手4第2天对阵2。这一天的对阵是1-3和2-4。t1day2i0时j1选手1第3天对阵4选手4第3天对阵1i1时j0选手2第3天对阵3选手3第3天对阵2。这一天的对阵是1-4和2-3。把整张表立起来看选手第1天第2天第3天1234214334124321和前面展示的4人表一模一样。这至少说明在n4这个最小规模上递归逻辑是自洽的。3.3 验证n8的关键步骤别只看前4行我见过很多人验证到n4就停了觉得递归嘛后面差不多。但n8才是真正检验理解度的地方因为这里会出现8个人、7天、每天4场比赛的完整结构。用上面的schedule(8)跑出来完整表长这样选手第1天第2天第3天第4天第5天第6天第7天1234567821436587341278564321876556781234658721437856341287654321注意看这个表的结构前3天左上方块是1到4的内部赛左下方块是5到8的内部赛后4天全部是跨组对抗。第4天是1-5、2-6、3-7、4-8第5天整体错位一位变成1-6、2-5、3-8、4-7第6天再错位第7天错到最后。这就是循环移位配对在8人规模上的完整形态。检查每一行比如选手5这一行是6、7、8、1、2、3、4确实把其他7个人都遇了一遍而且没有重复。这就是完整性和唯一性的最直接证据。3.4 复杂度与空间优化思路递归实现的时间复杂度很容易算。设T(n)为生成n人赛程的时间递归方程是T(n)2T(n/2)O(n²)。因为递归生成两个半区各n/2人合并阶段要把上半区、下半区各n/2行分别填n/2天还要填跨组对抗的n/2×n/2个格子总共O(n²)。解这个递推式结果是O(n²)。考虑到输出本身就有n(n-1)个格子O(n²)是最优数量级不存在渐进上更快的算法。空间上上面的实现每次递归都返回一个新矩阵递归深度log n如果每一层的临时矩阵都不释放累积空间是O(n² log n)。工程上更好的做法是直接开一个n×n的全局数组递归时传入行区间和天起始位置在原始数组上反复填充。这样空间复杂度能压到O(n²)而且少了很多拷贝开销。为了可读性我这里保留返回新表的写法但在实际项目里我建议改成原地递归版。下面是一个简化的原地递归思路能体会一下区别vectorvectorint table; // 全局表table[i][d] 表示第 i1 个选手第 d 天的对手 void fill(int left, int right, int dayBase) { int n right - left 1; if (n 2) { table[left][dayBase] right; table[right][dayBase] left; return; } int m n / 2; int mid left m - 1; fill(left, mid, dayBase); // 上半区内战 fill(mid 1, right, dayBase); // 下半区内战 int startDay dayBase m - 1; // 跨组对抗开始的天 for (int t 0; t m; t) { int day startDay t; for (int i 0; i m; i) { int j (i t) % m; table[left i][day] mid 1 j; table[mid j][day] left i; } } }这里的关键是把天数偏移和选手区间偏移同时处理好比返回新表的版本稍微难懂一点但效率更高也更接近很多教科书代码的表达方式。3.5 一个能自动排查错误的验证函数写完赛程生成器之后最怕的就是看着好像对实际某一行重复了一个对手。我强烈建议写一个自动验证函数用代码检查而不是用眼睛检查。bool validate(const vectorvectorint schedule, int n) { // 检查每行是否是 1..n 的一个排列 for (int i 0; i n; i) { vectorbool used(n 1, false); used[i 1] true; // 不能和自己比赛 for (int d 0; d n - 1; d) { int opp schedule[i][d]; if (opp 1 || opp n || used[opp]) { return false; } used[opp] true; } } // 检查对称性A 在某天遇到 BB 的同一天也必须遇到 A for (int i 0; i n; i) { for (int d 0; d n - 1; d) { int opp schedule[i][d]; if (schedule[opp - 1][d] ! i 1) { return false; } } } return true; }这个函数每次检查都是O(n²)的跑得很快。配合随机测试可以把n2、4、8、16都验一遍确认算法在各种规模下都正确。我在实际写这个算法的时候第一次对称性检查就没过因为跨组对抗时我只填了上半区选手视角那一行忘了同步反向格子。4. 经典四象限填表法好看但容易踩坑4.1 教科书里常见的那个思路很多教材讲完分治思想之后会给出一个看起来更优雅的填表方式直接把赛程表做成一个n×n的方阵左上角递归生成上半区的内部赛程然后通过四条简单的赋值把整个方阵填满。大致逻辑是左上块递归生成n/2人的赛程。右上块左上块每个元素加上n/2表示上半区选手对阵下半区对应选手。左下块右上块的某种转置保证下半区选手的反向视角。右下块直接复制左上块表示下半区的内部赛程。这个思路本身没错而且代码量看起来比我的循环移位版本少很多。但我在实践里踩过坑也看过不少同学在这个版本上翻车所以这里单独拎出来说。4.2 最容易翻车的点哪个格子是有效天数问题出在一个很隐蔽的地方。4个人单循环只需要3天但方阵是4×4的第4列如果按左上角元素n/2之类的规律硬填很容易填出一些怪数比如某一行出现3、4、1这种在第4天重复遇到对手的假数据。我在最初照着教材代码改写时就遇到过跑出来的8×8表第一行是2、3、4、5、6、7、8、1。前7列看着都对第8列是1也就是选手1第8天遇到自己这个格子其实是占位用的。真正的n人赛程只需要n-1天方阵多出的那一列本质上是对角线占位不应该被当成有效赛程。但很多人在复制左上块到右下块的过程中会把占位列也复制进去然后某一天就莫名出现选手自己打自己的情况。还有一个容易踩的坑是四条赋值的坐标关系。左上块是a[i][j]右上块应该写a[i][jm] a[i][j] m左下块应该是a[im][j] a[i][jm]也就是把右上块转置过来右下块是a[im][jm] a[i][j]。如果哪里坐标写反了结果不是重复就是越界。这个确实比循环移位版更容易写错。4.3 我的个人建议这几种实现各有取舍。循环移位版需要理解轮转思想但代码结构清晰跨组配对和内部赛程完全分离开不容易把占位列搞混。四象限填表法想法很优雅代码看着短但必须先在心里建立一个方阵多一列占位的心智模型否则很容易在边角区域写出自以为正确、实际错误的赋值。我的习惯是刷题或者理解算法时用循环移位版因为它和分治思想的对应关系最直白只有在需要背出一个最短代码应付考试时我才会考虑四象限法。如果你真心想彻底掌握这个问题我的建议是从循环移位版入手先手推n4再手推n8每一步都对照矩阵里的坐标。等彻底想明白了再去欣赏四象限填表法那种整体美感也不迟。5. 边界情况与真实赛制n不是2的幂怎么排5.1 赛场上几乎不会有16个队这种好事分治法要求n是2的幂但真实世界的比赛很少有刚好8个队、16个队的情况。6个队、10个队、12个队才是常态。这时候如果硬套上面的递归分治就会遇到切不开的问题6个人没法拆成两个相等的整数半区。一个非常实用的技巧是补虚选手。把报名人数向上补到最近的2的幂比如6个人就补到8个人多出来的两个位置填成轮空。任何选手抽到和虚选手比赛的那天就是他的休息日。这样虽然赛程天数变多了但结构依然可以用经典分治生成。具体来说6人比赛补齐成8人后赛程长度是7天。其中每个真实选手会在某些天遇到虚选手那天的比赛就不存在等于轮空。7天里每个人实际只打5场剩下两天休息。这个方案虽然比最优的5天要多两天但换来的是极其规整的赛程结构对于小规模比赛完全可接受。5.2 圆桌轮转法处理任意偶数n的通用方案如果你对多出的轮空天数不满意可以换一个更通用的办法圆桌轮转法也经常被叫做Berger表或者多边形法。这个办法不要求n是2的幂只要n是偶数就能直接排出n-1天的单循环赛程一天不浪费。规则是这样的固定选手1号把其余n-1个选手编号按顺序排成一个圆圈。第1轮圆圈尾部的选手对1号然后圆圈里剩下的偶数个选手按首尾配对的方式两两交手。下一轮让圆圈整体顺时针旋转一步重复同样的配对逻辑。这样滚动n-1轮之后每个选手恰好遇到其他所有人一次。我用n6给你演示一下这个直接看表最快轮次对阵第1轮1-6, 2-5, 3-4第2轮1-5, 6-4, 2-3第3轮1-4, 5-3, 6-2第4轮1-3, 4-2, 5-6第5轮1-2, 3-6, 4-5检查一下选手1在这5轮里依次遇到6、5、4、3、2刚好把其他5个人都遇了一遍选手2遇到5、3、6、4、1也没有重复。5天结束每天3场比赛正好排满。这个方案通用性强实现也不复杂我在实际参与组织一次社区羽毛球赛时就用它排过程序效果很稳。5.3 奇数人数怎么办奇数人数就更好处理了加一个虚拟的轮空选手就行。比如5个人补成一个虚拟的第6号。每个真实选手在和6号配对的那天休息其余4天正常比赛。这样5个人需要5天每天两场比赛加一个轮空。天数比理论下界的4天多一点这是奇数人数固有的代价绕不开。如果你还想压缩天数那就要引入不同赛制了比如小组赛加淘汰赛、瑞士轮等。这些赛制已经不追求任意两人都交手一次的强约束而是用积分或者淘汰规则在更少轮次里决出胜负。这类需求在现实中更常见但它属于另一个话题和这里的循环赛日程表分治问题已经不是一个量级。6. 这个算法在真正工程项目里的用处6.1 不只是作业题几个可以落地的场景循环赛日程表生成器最直接的应用就是赛事编排。小到单位内部的羽毛球赛、乒乓球赛大到围棋联赛、电竞联赛只要需要每两个队碰一次的单循环赛制这张表就能直接套用。第二个场景可能有点意外并行计算中的任务分发。在有些分布式训练或数据分片场景里需要让n个计算节点两两之间交换数据而且每一轮每个节点只能参与一次交换。这和循环赛的约束完全同构把选手换成计算节点把比赛换成数据交换任务分治法生成的就是一份无冲突的通信调度表。这个应用在某些矩阵转置、全量数据聚合的任务里是真实存在的。第三个场景是图论和组合设计。循环赛日程表的每一列本质上是一个完美匹配整个表就是完全图K_n的边集分解成n-1个完美匹配这在数学上叫1-因子分解。如果对算法背后的组合结构感兴趣这会是一个很好的切入点。6.2 构造性思维比答案本身更值钱我之所以觉得这个算法值得反复咀嚼是因为它体现了一种构造性证明的思维方式不是搜索一个解而是直接定义出一个永远合法的解。在很多实际系统里搜索解空间是不可行的比如n16时赛程的排列组合数量是天文数字暴力回溯根本跑不完但分治构造法可以瞬间生成一张合法表。这种把问题切小、各自搞定、再缝合的思路用在项目管理里也一样一个看起来无从下手的大型任务先切成两个半区让每个半区的负责人都能独立推进最后用一个明确的合并规则把两边接起来。这个合并规则就是整个系统最需要设计精妙的部分就像循环移位配对一样看似平淡实则保证了全局不重不漏。6.3 给正在啃算法的朋友几句实在话如果你是为了面试或者考试准备这个题目我的建议是别背代码先背过程。面试官问n8的赛程表怎么排你如果能当着他的面把表画出来并解释为什么第4到第7天是循环移位基本就过关了。如果只说得出用分治法左上角递归这种话大概率会被追问到卡壳。如果你是为了实际使用建议直接在现成的轮转法基础上改别从分治法往上凑。比如用我上面的schedule函数跑一次把结果输出成表格再自己写个脚本做轮空替换。很多项目管理工具其实也内置了赛程生成功能但自己写一遍能让你在改动需求时更有把握。最后手推一张n4的表只需要几分钟但这几分钟能让你真正理解递归展开的每一步在干什么。这个习惯我一直保留到现在遇到新的分治类问题也会先找一个最小的非平凡规模亲手把递归过程摊开验证一遍。这种笨办法反而是最省时间的捷径。