错位排列（Derangement）算法详解：从容斥原理到动态规划递推

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=3 开始，错位排列占全排列的比例越来越接近 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 = 0，D_2 = 1。

这个递推式是我个人最推荐的方式。原因有三：第一，它不需要计算阶乘，不会溢出；第二，它可以直接用动态规划从下往上填表；第三，它的推导过程本身就是对“错位”这个约束的深刻理解。

2.4 两种路线的取舍：什么时候用容斥，什么时候用递推

容斥公式适合做理论推导和证明极限性质，比如证明 D_n/n! → 1/e。递推适合写代码和实际计算，尤其是 n 较大的时候。

我做过一个简单的性能对比：n=20 时，容斥公式需要计算 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}) 来看，如果 n=2，需要 D_1 和 D_0，D_1=0，D_0=1，算出来 D_2 = 1×(0+1) = 1，正确。

所以 D_0 = 1 是合理的。但如果你在代码里从 n=1 开始循环，就要注意不要把 D_0 用错。我见过有人在 n=1 时返回 1，那就错了，因为 1 个元素不可能错位排列。

注意：D_0 = 1 是组合意义上的约定，不是递推必须的。写代码时建议单独处理 n=0 和 n=1 的情况，从 n=2 开始递推。

3.2 取模运算：大数场景下的处理技巧

算法题里经常要求结果对 10^9+7 取模。这时候递推式里的乘法 (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, n+1): 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 手算小规模：从 n=1 到 n=5 的完整推演

先手动推一遍，建立直觉。

n=1：只有 [1]，1 在原位，错位排列数 0。

n=2：排列有 [1,2] 和 [2,1]。[1,2] 两个都在原位，[2,1] 两个都不在原位。所以 D_2 = 1。

n=3：全排列 6 种。我们列出所有：

• [1,2,3]：全在原位，不行
• [1,3,2]：1 在原位，不行
• [2,1,3]：3 在原位，不行
• [2,3,1]：1→2，2→3，3→1，全部错位，可以
• [3,1,2]：1→3，2→1，3→2，全部错位，可以
• [3,2,1]：2 在原位，不行

所以 D_3 = 2。

n=4：用递推 D_4 = 3×(D_3+D_2) = 3×(2+1) = 9。

n=5：D_5 = 4×(D_4+D_3) = 4×(9+2) = 44。

手算到 n=5 就够了，再大就该写代码了。

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, n+1): 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(n+1): total += (-1)**k * math.comb(n, k) * math.factorial(n-k) return total

两个版本在 n ≤ 10 时结果一致。但 n=20 时，容斥版会因为阶乘溢出而报错，递推版依然正常。

4.3 动态规划填表：从 D_0 到 D_n 的完整过程

如果你习惯用数组存所有值，可以这样写：

def derangement_dp(n): dp = [0] * (n+1) dp[0] = 1 if n >= 1: dp[1] = 0 for i in range(2, n+1): 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})。前者在 n=2 时会算出 D_2 = 2×(0+1)=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 n=0 和 n=1 的边界处理

很多人在写循环时从 i=2 开始，但忘了处理 n=0 和 n=1 的输入。如果函数被调用时 n=0，返回 1；n=1，返回 0。这两个边界不处理，程序会出错或者返回错误结果。

5.4 常见问题速查表

5.5 一个容易忽略的坑：重复元素

错位排列的标准定义假设所有元素互不相同。如果元素有重复，比如 [1,1,2]，那“错位”的定义就模糊了——两个 1 交换位置算不算错位？这种情况下需要先做去重或者用带重复元素的错位排列公式，复杂度会高很多。实际工程里如果遇到重复元素，我建议先转成唯一标识再处理。

6. 错位排列的扩展与实战应用

6.1 错位排列在算法题中的变体

常见的变体包括：

• 求恰好 k 个在原位的排列数：C(n,k) × D_{n-k}
• 求至少 k 个在原位的排列数：Σ_{i=k}^{n} C(n,i) × D_{n-i}
• 带限制的错位排列：某些元素有额外的位置限制

这些变体在面试里经常出现，核心还是容斥和递推的组合。

6.2 在排班与分配系统中的应用

我做过一个排班系统，要求每个员工不能连续两周上同一个班次。这其实就是一个带约束的错位排列问题。把班次看成位置，员工看成元素，每周做一次错位排列，就能保证不重复。

实际实现时，我用递推算出总方案数，然后用随机化方法生成具体排班。这样既保证了公平性，又避免了人工排班的偏差。

6.3 在密码学与数据脱敏中的思路

密码重置时要求新密码不能和旧密码在相同位置有相同字符，这可以看作一个带字符集限制的错位排列。数据脱敏时，把敏感字段重新映射，也要求不能映射回原值，同样是错位排列的思想。

这些场景里，错位排列提供的是一个“最小扰动”的保证：既打乱了原始对应关系，又保证了每个元素都确实被移动了。

6.4 与递推、动态规划的通用思维

错位排列的递推式 D_n = (n-1)(D_{n-1}+D_{n-2}) 是动态规划里“分类讨论”的经典案例。它的思维方式可以迁移到很多问题：先固定一个元素的选择，然后根据这个选择引发的后续状态分类，最后合并。

我个人的体会是，把错位排列的递推推导过程反复推几遍，对理解动态规划的状态转移方程非常有帮助。它比背包问题简单，但包含了动态规划的核心要素：状态定义、边界条件、转移方程。

最后分享一个我常用的小技巧：如果你不确定递推式对不对，就手算 n=1 到 n=5，然后和已知序列 0, 1, 2, 9, 44 对比。对上了，基本就没问题。这个序列在 OEIS 上也能查到，编号 A000166，里面还有更多性质和生成函数，感兴趣可以顺着看下去。