1. 错位排列到底在解决什么问题第一次接触错位排列是在做一个抽奖系统的“防重复中奖”逻辑。当时的需求很简单年会抽奖已经中过奖的人不能再中但每个人初始都有一次机会。我一开始想用简单的随机打乱结果发现总有人连续中奖概率明显不对。后来才意识到这本质上是一个错位排列问题——每个元素都不能回到它原来的位置。错位排列英文叫derangement是组合数学里一个非常经典的概念。用最直白的话说有 n 个元素每个元素都有一个“原本的位置”现在要把它们重新排列要求每个元素都不在自己原来的位置上。这样的排列有多少种这个数量记作 D(n) 或者 !n。举个最常见的例子n 封信装进 n 个信封要求每封信都不装进对应的信封有多少种装法再比如n 个人交换礼物要求每个人都不能拿到自己带来的礼物有多少种交换方案这些场景的核心都是错位排列。它解决的问题很具体在“完全禁止原位”的约束下统计合法排列的总数。这个问题看起来简单但直接枚举会爆炸必须找到递推关系或者容斥公式。适合谁来学我觉得三类人最需要一是准备算法面试的错位排列是容斥原理和递推思想的经典考题二是做概率统计相关开发的比如抽奖、匹配、洗牌算法三是纯粹对组合数学感兴趣的这个问题的推导过程非常漂亮。我后面会从容斥原理和递推公式两条路分别推一遍再把代码实现、常见坑、以及实际项目里的变体都讲清楚。你不需要有很强的数学背景只要能看懂基本的排列组合符号剩下的我尽量用生活化的例子说明白。2. 两种核心推导思路容斥与递推2.1 用容斥原理一步步推出通项公式容斥原理的核心思想是先放开限制再把违反限制的情况减掉再加回多减的如此反复。错位排列的容斥推导是教科书级别的案例我把它拆成四步。第一步不考虑任何限制n 个元素的全排列有 n! 种。第二步减去“至少有一个元素在原位”的情况。设 A_i 表示第 i 个元素在原位的排列集合。如果第 i 个元素固定不动剩下 n-1 个元素随便排有 (n-1)! 种。一共有 n 个这样的集合所以减去 C(n,1) × (n-1)!。第三步加回“至少有两个元素同时在原位”的情况。因为第二步把这些情况减了两次。固定两个元素剩下 n-2 个随便排有 (n-2)! 种共有 C(n,2) 个组合所以加回 C(n,2) × (n-2)!。第四步依此类推交替加减。最终公式是D(n) n! × [1 - 1/1! 1/2! - 1/3! ... (-1)^n / n!]这个公式可以写成求和形式D(n) n! × Σ(k0 到 n) [(-1)^k / k!]我实测下来这个公式在 n 比较小的时候比如 n ≤ 10直接算完全没问题。但当 n 很大时n! 会迅速溢出即使你用 64 位整数也扛不住。所以工程上更常用的是递推公式下面细说。注意容斥公式里的交替符号非常容易写错。我见过不少人在代码里写成全部相加结果算出来的数字比 n! 还大那就明显不对了。记住第一项是减号k1 时第二项是加号。2.2 递推公式的两种形式与推导逻辑递推公式是我在实际编码里最常用的因为它不需要处理阶乘溢出而且可以边算边取模做算法题时经常要求对 1e97 取模。第一种递推形式D(n) (n-1) × [D(n-1) D(n-2)]这个公式的推导很有意思。考虑第 n 个元素它不能放在第 n 个位置所以它有 (n-1) 个可选位置。假设它放到了第 k 个位置k ≠ n。这时候分两种情况情况一第 k 个元素放到了第 n 个位置。那这两个元素互相交换了位置剩下的 n-2 个元素构成一个独立的错位排列有 D(n-2) 种。情况二第 k 个元素没有放到第 n 个位置。那我们可以把第 n 个位置“看成”是第 k 个元素原本的位置这样就变成了 n-1 个元素的错位排列有 D(n-1) 种。所以对于每一个 k都有 D(n-1) D(n-2) 种而 k 有 (n-1) 个选择乘起来就是 D(n) (n-1) × [D(n-1) D(n-2)]。第二种递推形式D(n) n × D(n-1) (-1)^n这个形式更简洁但推导稍微绕一点。它可以从容斥公式变形得到也可以用生成函数推。实际用的时候第一种更直观第二种在只需要单项计算时更快。基础值D(1) 0D(2) 1。这两个必须记牢否则递推会崩。D(1)0 是因为一个元素不可能不在原位D(2)1 是因为两个元素只有一种错位方式就是互换。2.3 两种方法的对比与选型建议对比维度容斥公式递推公式时间复杂度O(n) 每次从头算O(n) 可打表空间复杂度O(1)O(n) 或 O(1) 滚动大数溢出风险高涉及 n!低可边算边取模代码实现难度中等符号易错低适合场景数学推导、小 n 验证工程实现、算法题我的建议是做算法题一律用递推做数学证明用容斥。如果你要写一个工具函数反复调用先把 D(1) 到 D(MAXN) 打表存起来查询就是 O(1)。如果 MAXN 超过 20记得用大整数或者取模。3. 代码实现从暴力到高效3.1 暴力枚举验证小规模结果在写高效算法之前我习惯先用暴力法验证前几项确保自己的递推没写错。暴力法就是生成全排列然后检查每个元素是否都不在原位。from itertools import permutations def derange_brute(n): count 0 for perm in permutations(range(n)): if all(perm[i] ! i for i in range(n)): count 1 return count for n in range(1, 8): print(n, derange_brute(n))跑出来的结果是0, 1, 2, 9, 44, 265, 1854。这串数字你要记住后面调试的时候拿来对照非常方便。n3 时是 2n4 时是 9n5 时是 44。我见过有人把 n4 算成 8那就是漏了一种情况。提示暴力法只适合 n ≤ 8再大就跑不动了。n10 的全排列是 362 万还能忍n12 就是 4.79 亿直接卡死。3.2 递推打表的标准写法这是我最推荐的工程写法一次打表多次查询def build_derangement_table(max_n, modNone): D [0] * (max_n 1) if max_n 1: D[1] 0 if max_n 2: D[2] 1 for n in range(3, max_n 1): val (n - 1) * (D[n-1] D[n-2]) if mod: val % mod D[n] val return D # 不取模看真实值 table build_derangement_table(10) print(table[1:11]) # 输出: [0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961]如果你只需要第 n 项不需要整张表可以用滚动变量把空间压到 O(1)def derangement_n(n, modNone): if n 0: return 1 # 空集的错位排列定义为1 if n 1: return 0 prev2, prev1 0, 1 # D(1), D(2) for i in range(3, n 1): cur (i - 1) * (prev1 prev2) if mod: cur % mod prev2, prev1 prev1, cur return prev1这里有个细节D(0) 定义为 1。虽然直觉上“0 个元素的错位排列”有点怪但数学上为了递推自洽约定 D(0)1。你在写代码时如果遇到 n0 的边界直接返回 1 就行。3.3 大数场景下的取模处理算法题里经常要求结果对 1e97 取模。这时候递推公式的优势就体现出来了每一步都是加法和乘法可以随时取模不会溢出。但容斥公式就不行因为里面有除法除以 k!取模需要求逆元麻烦得多。MOD 10**9 7 def derangement_mod(n): if n 0: return 1 if n 1: return 0 prev2, prev1 0, 1 for i in range(3, n 1): cur (i - 1) * (prev1 prev2) % MOD prev2, prev1 prev1, cur return prev1 print(derangement_mod(100000))这个写法在 n100000 时瞬间出结果完全不会溢出。我实测过 n10^6 也就几十毫秒。注意取模的时候(i-1) 本身可能很大但 Python 会自动处理大整数所以不用担心中间溢出。如果你用 C 或 Java记得用 long long并且先取模再乘避免 (i-1) * (prev1 prev2) 溢出。4. 常见问题与排查技巧实录4.1 递推基础值写错导致全盘崩溃这是我最常踩的坑。D(1) 和 D(2) 一旦写错后面所有项都是错的。我见过有人把 D(1) 写成 1结果整个表偏移。记住D(1)0D(2)1。如果你不确定用暴力法跑 n1 到 5 对照一下。还有一个隐蔽的坑循环从 n3 开始但如果你把 D(0) 也初始化了要确保 D(0)1 而不是 0。有些模板代码里 D 数组默认全是 0然后只设了 D[1] 和 D[2]结果 n0 查询时返回 0但正确答案应该是 1。4.2 容斥公式符号错误的排查方法容斥公式的符号是交替的写代码时很容易漏掉 (-1)^k。一个简单的自检方法算出来的 D(n) 必须小于 n!。如果你算出的值大于等于 n!那一定是符号错了或者某项漏了。另一个自检D(n) 和 n! 的比值趋近于 1/e ≈ 0.3679。当 n 比较大时比如 n ≥ 8D(n)/n! 应该非常接近 0.3679。如果偏离很远说明公式实现有问题。常见错误现象修正方法D(1) 写成 1所有项偏移改为 0容斥符号全加结果 n!改为交替加减循环从 n2 开始D(2) 被覆盖从 n3 开始取模时先加后乘溢出结果异常先取模再乘忘记 D(0)1n0 查询错误显式初始化4.3 实际项目中的变体与扩展错位排列在实际项目里很少以“纯数学题”的形式出现更多是变体。我遇到过的有变体一部分错位。要求恰好有 k 个元素在原位其余错位。这个用组合数乘一下就行C(n,k) × D(n-k)。比如 n5恰好 2 个在原位方案数就是 C(5,2) × D(3) 10 × 2 20。变体二带权错位。每个元素不能去某些特定位置但不一定是自己的原位。这就变成了二分图匹配计数问题一般用状态压缩 DP 做n 小的时候可行。变体三循环错位。要求每个元素不能在自己原位且整体构成一个循环。这个数量是 (n-1)!因为固定第一个元素的位置后剩下的就是圆排列。提示如果你在面试里遇到“错位排列”的题先问清楚是求数量还是求具体方案。求数量用递推求方案用回溯或 DP。两者难度差很多。5. 从数学到工程错位排列的实际应用场景5.1 抽奖与随机匹配中的防重复逻辑回到我开头提到的抽奖系统。当时的需求是“已中奖者不再参与后续抽奖”但更严格的要求是“每个人都不能抽到自己”。这其实就是错位排列的应用。具体做法把参与者编号 0 到 n-1生成一个错位排列作为“抽奖映射”。第 i 个人抽到第 perm[i] 个人的奖品。因为 perm 是错位排列所以每个人都不会抽到自己。生成一个随机错位排列的算法我用的是“拒绝采样”先随机打乱检查是否是错位排列不是就重来。当 n 比较大时命中概率约 1/e ≈ 36.8%平均试 2.7 次就能成功效率可以接受。如果你要生成大量错位排列拒绝采样就有点慢了。可以用“基于递推的构造法”从 n 开始每次决定第 n 个元素放到哪个位置然后递归处理剩下的。这个构造法的时间复杂度是 O(n)而且保证一次成功。5.2 算法面试中的高频考法与应对错位排列在面试里通常不会直接问“什么是错位排列”而是包装成场景题。我整理了几种常见问法问法一n 个人交换礼物每个人都不能拿到自己的有多少种方案——直接套 D(n)。问法二n 对夫妻跳舞每对夫妻不能互为舞伴有多少种配对——这是错位排列的变体答案是 D(n)。问法三一个数组要求每个元素都不在原来的下标上有多少种重排方式——还是 D(n)。问法四求 D(n) 对 1e97 取模。——用递推注意取模。面试时如果你能主动说出“这是错位排列问题可以用递推 D(n)(n-1)(D(n-1)D(n-2)) 求解”基本就稳了。如果再能补一句“容斥公式是 n! × Σ(-1)^k/k!”面试官会觉得你基础很扎实。5.3 与其他排列问题的边界区分错位排列容易和几个概念混淆我列一下区别概念核心约束公式全排列无约束n!错位排列每个元素不在原位D(n)圆排列首尾相接旋转视为相同(n-1)!部分错位恰好 k 个在原位C(n,k) × D(n-k)禁位排列每个元素有禁位集合容斥或 DP禁位排列是错位排列的推广错位排列是禁位排列的特例每个元素的禁位集合就是它自己的原位。如果你能理解错位排列的容斥推导禁位排列的容斥推导就是把“固定一个元素”换成“固定一个禁位”思路完全一样。6. 我踩过的坑与实操心得6.1 递推打表的边界处理经验打表的时候数组大小一定要开到 max_n 1否则查询 D(max_n) 时会越界。我见过有人开 max_n 大小然后循环到 max_n结果最后一个元素写不进去。这个 bug 很隐蔽因为 Python 会抛 IndexError但 C 不会它会默默写越界内存导致后面数据莫名其妙出错。另一个经验如果你要多次查询不同的 n打表是最优解。但如果你只查一次滚动变量更省内存。我一般会写两个函数一个 build_table 用于批量查询一个 derangement_n 用于单次查询。6.2 取模运算中的常见陷阱取模的时候减法要特别小心。虽然错位排列的递推公式里只有加法和乘法但如果你用容斥公式就会有减法。在取模意义下a - b 要写成 (a - b MOD) % MOD否则可能出现负数。还有一个坑如果你用第二种递推形式 D(n) n × D(n-1) (-1)^n取模时 (-1)^n 要处理成 MOD-1 或 1。我一般直接判断奇偶n 为奇数时加 MOD-1偶数时加 1。提示做算法题时如果题目没说要取模但 n 很大你也要主动取模否则结果会溢出。很多在线判题系统对溢出是直接判错的。6.3 性能优化的几个实用技巧如果你需要计算 D(n) 对多个不同的模数取模打表就不太方便了因为表是针对特定模数的。这时候可以用滚动变量每次重算时间复杂度 O(n)对于 n ≤ 10^6 完全够用。如果 n 特别大比如 10^9那就不能用 O(n) 递推了需要用矩阵快速幂。错位排列的递推可以写成矩阵形式[D(n), D(n-1)]^T [[n-1, n-1], [1, 0]] × [D(n-1), D(n-2)]^T但注意矩阵里的 n-1 是变化的所以不能直接用固定矩阵快速幂。实际上错位排列没有简单的固定矩阵快速幂形式因为系数随 n 变化。所以 n 特别大时一般还是用容斥公式配合快速阶乘算法但那个实现复杂度很高实际项目中很少遇到。我个人的经验是n ≤ 10^6 用递推n 10^6 考虑近似值 D(n) ≈ n!/e。当 n 很大时D(n)/n! 趋近于 1/e如果你只需要比值直接用 1/e 就行误差小于 1/(n1)!。6.4 一个容易被忽略的细节D(0) 的定义最后说一个很多人忽略的点D(0) 1。这个定义在数学上是合理的因为“0 个元素的排列”只有一种空排列而空排列满足“每个元素都不在原位”的条件因为没有元素违反。在代码里如果你不处理 n0遇到边界查询就会出错。我在一个项目里就因为这个 bug 排查了半天用户输入 0 时系统返回 0但业务逻辑期望返回 1导致后续计算全部偏移。后来我在函数入口加了if n 0: return 1才解决。这个坑不常遇到但遇到一次就够你记一辈子。错位排列这个主题从数学推导到代码实现再到实际应用每一层都有值得深挖的细节。我上面写的这些基本都是我在实际项目和面试准备中积累下来的经验希望能帮你少走一些弯路。如果你在实现过程中遇到其他奇怪的问题欢迎一起交流。