错排问题

数学学科概念

n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。

基本信息

错排问题是组合数学发展史上的一个重要问题，错排数也是一项重要的数。令是的一个错排，如果每个元素都不在其对应下标的位置上，即，那么这种排列称为错位排列，或错排、重排（Derangement）。

我们从分析1 2 3 4的错排开始：

1 2 3 4的错排有:

4 3 2 1，4 1 2 3，4 3 1 2，

3 4 1 2，3 4 2 1，2 4 1 3，

2 1 4 3，3 1 4 2，2 3 4 1。

第一列是4分别与123互换位置，其余两个元素错排。

1 2 3 4→4 3 2 1，

1 2 3 4→3 4 1 2，

1 2 3 4→ 2 1 4 3

第2列是4分别与312（123的一个错排）的每一个数互换

3 1 2 4→4 1 2 3，

3 1 2 4→3 4 2 1，

3 1 2 4→3 1 4 2

第三列则是由另一个错排231和4换位而得到

2 3 1 4→4 3 1 2，

2 3 1 4→2 4 1 3，

2 3 1 4→2 3 4 1

上面的分析结果，实际上是给出一种产生错排的结果。

错排公式

递推关系

为求其递推关系，分两步走：

第一步，考虑第n个元素，把它放在某一个位置，比如位置k，一共有n-1种放法；

第二步，考虑第k个元素，这时有两种情况：（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有种放法；（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有种放法。

根据乘法和加法法则，综上得到

特殊地，。此外，存在

因此，。

通项公式求解

下面利用递推关系证明通项公式，可利用母函数方法，也可利用容斥原理。首先基于母函数方法进行证明，令

有递推关系得

因此，，

而1/（1-x）可以替换成无穷级数（无穷递缩等比数列）

故（由对应次数项系数相等）

此外，也可基于容斥原理进行证明。设为数i在第i位上的全体排列，。则有

故每个元素都不在原来的位置上的排列数为

错排生成算法

上面对错排公式进行了证明，在实际应用中，为得到所有合理的错排方案，当n较大时，手动枚举费时费力，需要程序依照算法生成所有错排方案。因此下面分别研究了递归法、基于字典序的筛选法和改进字典序法的算法思想、流程和程序实现。

递归法

递归法的思想为逐位安排：首先安排第一位，并记录被安排的数，然后递归，同样的方法安排第二位……直到安排到到第n位。若第n位满足错排，则错排方案数加一，并输出该错排，并返回；否则直接返回，返回后，撤销该位安排的数。其中，安排每一位时，都遍历了n个数，下一位的递归返回后都撤销这位安排的数，然后遍历到下一个数，重新递归。这样通过不断遍历和递归，实现了所有错排方案的生成。算法伪代码如下：

为了更清晰地描述算法，下图给出算法流程，其中Rec(x)为安排第x位的递归函数。

基于字典序的筛选法

基于字典序的筛选法的思想非常简单，即首先按照字典序生成每一个排列，然后检验生成的该排列是否满足错排，如果是则方案数加一并输出，否则生成下一个排列。算法流程如下图所示。

改进字典序法

改进字典序法是在字典序的基础上改进而成，主要思想是：按照字典序，一旦出现不满足错排的排列，则由此开始跳过接下来的不满足错排的一些排列。由于避免了长段的非错排的排除流程，因此相对传统字典序法能够提高算法效率。算法流程如下图所示。

图中，i表示安排第i位，Flag表示不满足错排的元素的位置，均满足则默认为n+1。蓝色方框表示根据字典序找下一个排列，并记录其不满足错排的Flag。红色方框表示根据算法规则跳过接下来的不满足错排的一些排列，然后寻找关键位置，给此位置安排满足错排的数。蓝色方框部分只需根据字典序生成下一个排列，并记录最左侧不满足错排的元素位置为Flag即可，具体流程不再赘述。下面给出错排的一个引理，然后给出红色方框的算法流程。

引理1：给定一个不满足错排的排列P1，在全排列的字典序中的下一个排列记为P2，在错排的字典序中的下一个排列记为P3。设P1中不满足错排的最左侧的元素下标为i，P1和P2从左侧开始比较第一个不相等的元素的下标记为j，P1与P3从最左侧开始比较第一个不相等的元素的下标记为k，则一定有k≤min{i, j}。

例如：错排P1=23541，则P2=P3=24135，i=4，j=k=2，成立。

再如：错排P1=42513，则P2=42531，P3=43152，j=k=2，i=4，成立。

引理1的证明很简单，j即为根据字典序法从右往左找到的第一个下降的位置。如果ij，说明错排的位置在j的后面，此时调整j及其后面的元素位置得到的排列就改变了原先不满足错排的元素位置，因此新排列可能满足错排，此时k≤j，因此得证。

根据引理1，红色方框的算法流程为：

为了更清晰地说明算法流程，以n=5为例给出以下结果：

根据上述分析及举例可见，改进字典序法相对基于字典序的筛选法有以下优点：

为保证算法可延续性，末尾元素的设定忽略了错排规则，生成后再判断，否则算法可能会无法继续，如n=5时算法起始21435的生成。

遍历法

文献[2]给出一种常数时间的错排生成算法，其本质属于遍历法，下面以n=5为例说明其算法：

第一步：将最后一位数移至第一位，其余的数顺次向后移动，产生错排d。

如：12345→51234。

第二步：考察d的第二个位置，除去第一个位置的数和2不能放在这个位置上，其余均可。

如：51234→51234或53214或54231。

考察d的第三个位置，除去第一、第二个位置上的数和3不能放在这个位置上，其余的数都可以。

如：51234→51234→51234或51432

51234→53214→53214或53124或53412

51234→54231→54231或54132

以此类推，n个数的错排一直考察到第n个位置为止，结束第二步。

第三步：重复第一、第二步的过程，循环这个程序。

如：12345→51234→45123→34512→23451。

这个循环过程直到第一步产生234⋯(n-1)(n)1，继续执行第二、三步，然后结束。

在算法实现上，生成每一个排列采用无循环处理，时间复杂度为O(1)，因此生成所有错排的时间复杂度为。

性能分析

上面详述了四种算法思想和流程，下面给出各算法的复杂度分析和性能比较。

对于递归法，n个元素的错排方案数为，每个错排均需遍历到，因此基本复杂度为。递归函数其中有n次循环，若不考虑错排规则，则每次循环均调用递归函数，考虑错排规则时调用次数满足，因此。但由于递归函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以，考虑函数处理过程，整体看来，递归法的效率并不高。

对于基于字典序的筛选法，字典序法的复杂度为，对每个排列检验其是否为错排的复杂度为，因此该算法的时间复杂度为。

对于改进字典序法，由于其相对基于字典序的筛选法的优点，所以复杂度必然会降低。由于算法中逻辑判断与处理很多，分析其复杂度非常困难。但由于其跳过了大部分的非错排，因此复杂度大约为。因此，改进字典序法和文献[2]提出的方法的复杂度大体相同。

综合上述分析可见，算法总体效率大致为：改进字典序法≈文献[2]方法＞基于字典序的筛选法＞递归法。下面根据数值实验结果给出各算法的性能比较。

表各算法运行耗时比较（单位：ms）

表1给出了各算法运行耗时比较，图4给出了运行时间随n变化的对数曲线图。从上述结果可知，改进字典序法和文献[2]方法的性能相当，前者稍好一些。这两种算法的运行耗时大约为基于字典序的筛选法的一半，而筛选法的运行耗时大约为递归法的一半。注意：由于所取n值在10附近，且曲线纵坐标取log10(t)，因此所得结果大致为直线，只能说明n取10左右时，曲线局部为近似直线，并不说明整体都成此特性。总之，数值实验分析结果与上述时间复杂度分析结果一致。

C++代码

递归实现

基于字典序实现

改进字典序法实现

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市

云南省