1. 错位排列到底在解决什么问题第一次接触“错位排列”这个词很多人会以为它只是排列组合里的一个小分支考试里顶多考一道填空题。但真正做过算法题、写过排班系统、处理过数据脱敏的人会告诉你这个看似简单的概念背后牵扯的是容斥原理、递推关系、动态规划甚至概率期望的一整套思维链条。先把定义说清楚。错位排列英文叫 derangement指的是一个排列中没有任何一个元素出现在它原本的位置上。比如三个元素的排列 [1,2,3]它的全排列有 6 种但其中满足“每个数都不在自己位置上”的只有 [2,3,1] 和 [3,1,2] 两种。这两个就是 3 个元素的错位排列。它解决的问题非常具体当你有一组元素和一组位置要求“谁都不能回到自己的老位置”时有多少种安排方式。这个问题在现实里到处都是——老师重新批改试卷时要求学生不能拿到自己的卷子公司年会抽礼物时要求不能抽到自己带来的礼物密码重置时要求新密码不能和旧密码有任何位置上的字符重合甚至编译器做寄存器分配时也要避免把变量放回它刚被移出的位置。适合谁来深入我认为三类人最该把错位排列吃透一是准备算法面试的人因为它是容斥原理和递推的经典结合二是做后端或数据开发的人排班、分配、去重逻辑里经常需要它三是教组合数学的老师错位排列是讲清楚“容斥”最漂亮的例子之一。但很多教程只给公式不讲推导导致读者背了 D_n (n-1)(D_{n-1}D_{n-2}) 却不知道它怎么来的更不知道什么时候该用容斥、什么时候该用递推。我写这篇东西就是想把这个概念从“背公式”拉到“能自己推、能写代码、能判断该用哪种方法”的层面。2. 从全排列到错位排列核心思路拆解2.1 为什么不能直接数全排列与错位排列的差距n 个元素的全排列数量是 n!这个增长非常快。4 个元素是 24 种5 个元素是 120 种10 个元素就是 362 万多种。错位排列的数量虽然比全排列少但也不是能靠手数解决的。n 个元素的错位排列数量记作 D_n 或 !n。前几个值是n全排列 n!错位排列 D_n占比1100%22150%36233.3%424937.5%51204436.7%672026536.8%75040185436.8%你会发现一个很有意思的现象从 n3 开始错位排列占全排列的比例越来越接近 1/e ≈ 0.3679。这不是巧合后面讲容斥的时候会看到这个极限是怎么自然冒出来的。那为什么不能直接数因为“没有任何一个元素在原本位置”这个条件是一个多条件同时满足的问题。你要排除“第1个元素在原位”的情况还要排除“第2个元素在原位”的情况同时还要把“第1个和第2个同时原位”的情况加回来。这就是容斥原理的典型场景。2.2 容斥原理路线从“至少一个在原位”反推容斥原理的核心思想是要算“一个都不在原位”的排列数可以先算“至少有一个在原位”的排列数然后用总数减掉。设 A_i 表示“第 i 个元素在原位”的排列集合。我们要求的是所有 A_i 都不发生的排列数也就是 |A_1^c ∩ A_2^c ∩ ... ∩ A_n^c|。根据容斥原理D_n n! - C(n,1)(n-1)! C(n,2)(n-2)! - C(n,3)(n-3)! ... (-1)^n C(n,n)0!化简一下。C(n,k)(n-k)! n! / k!所以D_n n! × (1 - 1/1! 1/2! - 1/3! ... (-1)^n / n!)这个公式非常漂亮。它把错位排列和自然常数 e 联系起来了。当 n 趋于无穷时括号里的部分就是 e^{-1}所以 D_n ≈ n!/e。我实际算的时候如果 n 比较小比如 n ≤ 10直接用这个公式手算或者写代码都很方便。但要注意当 n 很大时n! 会溢出所以工程上更常用递推。2.3 递推路线D_n 与 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_1 0D_2 1。这个递推式是我个人最推荐的方式。原因有三第一它不需要计算阶乘不会溢出第二它可以直接用动态规划从下往上填表第三它的推导过程本身就是对“错位”这个约束的深刻理解。2.4 两种路线的取舍什么时候用容斥什么时候用递推容斥公式适合做理论推导和证明极限性质比如证明 D_n/n! → 1/e。递推适合写代码和实际计算尤其是 n 较大的时候。我做过一个简单的性能对比n20 时容斥公式需要计算 20!这个数大约是 2.4×10^18用 64 位整数已经溢出了而递推只需要存两个变量迭代 20 次就出结果。所以工程上几乎都用递推。但容斥的价值在于它让你明白为什么错位排列的概率会趋近于 1/e。这个结论在概率论和随机算法里经常出现比如“随机打乱一个数组没有任何元素留在原位的概率约等于 36.8%”。3. 核心细节解析与实操要点3.1 初始条件的坑D_0 到底等于几很多人在写递推的时候会纠结 D_0 的值。从组合意义上说0 个元素的错位排列只有一种就是“什么都不做”所以 D_0 1。但从递推式 D_n (n-1)(D_{n-1}D_{n-2}) 来看如果 n2需要 D_1 和 D_0D_10D_01算出来 D_2 1×(01) 1正确。所以 D_0 1 是合理的。但如果你在代码里从 n1 开始循环就要注意不要把 D_0 用错。我见过有人在 n1 时返回 1那就错了因为 1 个元素不可能错位排列。注意D_0 1 是组合意义上的约定不是递推必须的。写代码时建议单独处理 n0 和 n1 的情况从 n2 开始递推。3.2 取模运算大数场景下的处理技巧算法题里经常要求结果对 10^97 取模。这时候递推式里的乘法 (n-1)(D_{n-1}D_{n-2}) 要先加后乘再取模不能先取模再乘否则可能出错。正确的顺序是MOD 10**9 7 def derangement_mod(n): if n 0: return 1 if n 1: return 0 d0, d1 1, 0 for i in range(2, n1): d2 (i-1) * (d1 d0) % MOD d0, d1 d1, d2 return d1这个写法用滚动变量空间复杂度 O(1)时间复杂度 O(n)。n 到 10^6 都能秒出。3.3 容斥公式的数值稳定性问题如果你非要用容斥公式算比如 D_n n! × Σ(-1)^k / k!那在浮点数下会有精度问题。因为 n! 很大而求和部分在 0.3679 附近两者相乘会放大误差。我的经验是如果只需要近似值可以用 D_n ≈ n!/e然后四舍五入。这个近似在 n ≥ 5 时误差已经小于 1。如果需要精确值还是用递推。3.4 错位排列与“至少 k 个在原位”的推广有时候问题不是“一个都不在原位”而是“恰好有 k 个在原位”。这时候可以先选出哪 k 个在原位剩下的 n-k 个错位排列数量 C(n,k) × D_{n-k}这个推广在排班场景里很有用。比如 10 个人重新分配工位要求恰好有 3 个人留在原工位其余 7 人必须换方案数就是 C(10,3) × D_7。4. 实操过程与核心环节实现4.1 手算小规模从 n1 到 n5 的完整推演先手动推一遍建立直觉。n1只有 [1]1 在原位错位排列数 0。n2排列有 [1,2] 和 [2,1]。[1,2] 两个都在原位[2,1] 两个都不在原位。所以 D_2 1。n3全排列 6 种。我们列出所有[1,2,3]全在原位不行[1,3,2]1 在原位不行[2,1,3]3 在原位不行[2,3,1]1→22→33→1全部错位可以[3,1,2]1→32→13→2全部错位可以[3,2,1]2 在原位不行所以 D_3 2。n4用递推 D_4 3×(D_3D_2) 3×(21) 9。n5D_5 4×(D_4D_3) 4×(92) 44。手算到 n5 就够了再大就该写代码了。4.2 代码实现Python 递推版与容斥版对比递推版def derangement_recursive(n): if n 0: return 1 if n 1: return 0 d0, d1 1, 0 for i in range(2, n1): d0, d1 d1, (i-1) * (d1 d0) return d1 for n in range(1, 11): print(n, derangement_recursive(n))输出1 0 2 1 3 2 4 9 5 44 6 265 7 1854 8 14833 9 133496 10 1334961容斥版import math def derangement_inclusion(n): total 0 for k in range(n1): total (-1)**k * math.comb(n, k) * math.factorial(n-k) return total两个版本在 n ≤ 10 时结果一致。但 n20 时容斥版会因为阶乘溢出而报错递推版依然正常。4.3 动态规划填表从 D_0 到 D_n 的完整过程如果你习惯用数组存所有值可以这样写def derangement_dp(n): dp [0] * (n1) dp[0] 1 if n 1: dp[1] 0 for i in range(2, n1): dp[i] (i-1) * (dp[i-1] dp[i-2]) return dp[n]这个版本的好处是如果你需要查询多个 n 的错位排列数可以一次填表后面 O(1) 查询。4.4 实际场景年会抽礼物不能抽到自己假设公司年会10 个员工每人带一份礼物重新随机分配要求每个人都不能拿到自己带来的礼物。问有多少种分配方案这就是 D_10。用递推算出来是 1334961。总排列数是 10! 3628800。所以概率是 1334961 / 3628800 ≈ 0.3679正好接近 1/e。如果你要写一个程序来随机分配并验证这个概率可以这样做import random def random_derangement(items): n len(items) while True: shuffled items[:] random.shuffle(shuffled) if all(shuffled[i] ! items[i] for i in range(n)): return shuffled这个拒绝采样的方法在 n 较小时效率还可以因为命中概率约 36.8%。但 n 很大时虽然概率不变但每次 shuffle 是 O(n)总体期望还是 O(n)可以接受。5. 常见问题与排查技巧实录5.1 递推式记错了怎么办最常见的错误是把 D_n (n-1)(D_{n-1}D_{n-2}) 记成 D_n n(D_{n-1}D_{n-2}) 或者 D_n (n-1)(D_{n-1}-D_{n-2})。前者在 n2 时会算出 D_2 2×(01)2但实际是 1后者会出现负数。我的记忆方法是第 n 个元素有 n-1 个位置可选每种选择对应 D_{n-1}D_{n-2} 种后续。所以系数是 n-1括号里是加号。5.2 取模时出现负数如果你在递推过程中做了减法比如某些变体问题取模后可能出现负数。Python 里 % 会自动处理成正数但 C 和 Java 里不会。保险做法是d2 ((i-1) * ((d1 d0) % MOD)) % MOD;如果涉及减法加一个 MOD 再取模d2 (d2 - something MOD) % MOD;5.3 n0 和 n1 的边界处理很多人在写循环时从 i2 开始但忘了处理 n0 和 n1 的输入。如果函数被调用时 n0返回 1n1返回 0。这两个边界不处理程序会出错或者返回错误结果。5.4 常见问题速查表问题现象可能原因解决方法n2 算出 2递推系数写成 n改成 n-1n3 算出 1初始条件 D_2 写成 0D_2 1大 n 结果溢出用了容斥公式算阶乘改用递推取模后结果不对乘法前没取模先加后乘再取模n0 报错没处理边界单独返回 1概率不接近 0.368n 太小n ≥ 5 后再看5.5 一个容易忽略的坑重复元素错位排列的标准定义假设所有元素互不相同。如果元素有重复比如 [1,1,2]那“错位”的定义就模糊了——两个 1 交换位置算不算错位这种情况下需要先做去重或者用带重复元素的错位排列公式复杂度会高很多。实际工程里如果遇到重复元素我建议先转成唯一标识再处理。6. 错位排列的扩展与实战应用6.1 错位排列在算法题中的变体常见的变体包括求恰好 k 个在原位的排列数C(n,k) × D_{n-k}求至少 k 个在原位的排列数Σ_{ik}^{n} C(n,i) × D_{n-i}带限制的错位排列某些元素有额外的位置限制这些变体在面试里经常出现核心还是容斥和递推的组合。6.2 在排班与分配系统中的应用我做过一个排班系统要求每个员工不能连续两周上同一个班次。这其实就是一个带约束的错位排列问题。把班次看成位置员工看成元素每周做一次错位排列就能保证不重复。实际实现时我用递推算出总方案数然后用随机化方法生成具体排班。这样既保证了公平性又避免了人工排班的偏差。6.3 在密码学与数据脱敏中的思路密码重置时要求新密码不能和旧密码在相同位置有相同字符这可以看作一个带字符集限制的错位排列。数据脱敏时把敏感字段重新映射也要求不能映射回原值同样是错位排列的思想。这些场景里错位排列提供的是一个“最小扰动”的保证既打乱了原始对应关系又保证了每个元素都确实被移动了。6.4 与递推、动态规划的通用思维错位排列的递推式 D_n (n-1)(D_{n-1}D_{n-2}) 是动态规划里“分类讨论”的经典案例。它的思维方式可以迁移到很多问题先固定一个元素的选择然后根据这个选择引发的后续状态分类最后合并。我个人的体会是把错位排列的递推推导过程反复推几遍对理解动态规划的状态转移方程非常有帮助。它比背包问题简单但包含了动态规划的核心要素状态定义、边界条件、转移方程。最后分享一个我常用的小技巧如果你不确定递推式对不对就手算 n1 到 n5然后和已知序列 0, 1, 2, 9, 44 对比。对上了基本就没问题。这个序列在 OEIS 上也能查到编号 A000166里面还有更多性质和生成函数感兴趣可以顺着看下去。