C++离散与组合数学之如何让错排列一步错，步步错！

一枚大果壳

发布于 2024-04-02 15:58:17

860

发布于 2024-04-02 15:58:17

文章被收录于专栏：编程驿站编程驿站

1. 前言

错排列是排列里的特殊数体。本文和大家聊聊错排列的定义以及如何枚举出所有的错排列。现实生活中，错排列的应用也较广泛，研究错排列可以丰富排列与组合相关知识的认知。

2. 错排列

错排列是组合数学中的一个重要理论分支。了解错排列，先从错排列的概念入手。

概念：理论上，n个有序的元素应有n!种不同的全排列，如果其中有一个排列使得所有的元素不在原来的位置上，则称这个排列为错排或者叫重排。如，1 2的错排是唯一的，即2 1。1 2 3的错排有3 1 2、2 3 1。这二者可以看作是1 2错排，3分别与1、2换位而得的。

那么，对于长度为n的数列，到底有多少种错排列？这些错排列具体又是哪些？带着这些问题，我们继续深入讲解。

2.1 统计数量

如果有 1 2 3 4 四个数字，由它们所组成的错排列有多少？

简单粗暴的方式，在纸上手工一一枚举。即使是纯手工过程，也有讲究。

创建长度为4的数列，每一个数字存储在与其下标相同的单元格中。如下图所示：

数字4分别与数字1,2,3交换位置，然后其它数字进行错排列。如下图会产生 3 种错排列数列。

数字4和1 2 3的一个错排数3 1 2中的每一个数字交换位置。如下图其有3种情况。

数字4和1 2 3的一个错排数2 3 1中的每一个数字交换位置。

统计可知，1 2 3 4四个数字共有9种错排列。使用上述的推演过程，可知常用错位排列数：

3个元素的错位排列有2种
4个元素的错位排列有9种
5个元素的错位排列有44种

当元素较少时，短时间内可以推演出错排列的数量。当元素较多时，纯手工的推演计算必是一件吃苦不讨好的事情。需要找出错排列在排列过程中的规律，总结出通用的表达式，方能一劳永逸。

其实，在统计错排列数量时，存在一种递归思想：

假设原始数列共有n个数字，第n个数字和其它数字共有n-1种交换方式。

分析第k位置的元素。如果其已经和第n个元素交换，则剩下n-2个元素的错排列Dn-2。

如果k不在n所在位置，这时剩下n-1个元素的错排有Dn-1。

根据乘法和加法原理，可归纳出如下的递归表达式：

Dn=(n-1)(Dn-1+Dn-2)。

递归出口：当n=1时，D1=0，当n=2时，D2=1把上述表达式展开，可得到更通用的表达式：Dn=nDn-1+(-1)n,D1=0。

C++实现递归算法：

#include <iostream>
#include <cmath> 
using namespace std;
int cpl(int n){
 if(n==1)return 0;
 return n*cpl(n-1)+pow(-1,n);
}
int main(int argc, char** argv) {
 int n;
 cin>>n;
 int c=cpl(n);
 cout<<c<<endl;
 return 0;
}

分别输入3、4、5可知到结果：2、9、44。

2.2 枚举所有

除了可以使用递推算法计算错排列数量。还存在一种通项公式：

到目前为止，已能计算出错排列的数量。如果需要查询出所有错排列，可以使用回溯算法、BFS搜索算法和筛选法。下面介绍回溯和BFS。

回溯算法

回溯算法本质是深度优先搜索。在求解全排列时，我们使用过此算法。错排列仅是全排列中的一种特殊存在，只需要在求全排列的回溯算法基础之上，增加某些稍苛刻的条件即可。所以，关键是找出过滤条件。

如下图所示，把1 2 3 4 填入4个单元格，对于任一单元格中数字要求有2点:

不能是已经被使用过的数字。
和位置编号相同的数字不能填入。

如下图，在向第一个单元格中填数字时，数字1不能填入，只能在2、3、4中选择其中的一个填入。

在向第二个单元格填数字时，如果数字3已经填入在第一个单元格，则不能再填入第二个单元格，因数字2与单元格的位置编号相同，也不能填入，除此之外的1、4s可填入。

基于上述的要求，C++回溯算法实现错排列：

#include <iostream>
#include <cmath>
using namespace std;
//错排列结果
int res[100]= {0};
//数字是否已经使用
int vis[100]= {0};
//错排列数字数量
int n;
//计数器 
int count=0;
//输入结果
void show() {
 for(int i=1; i<=n; i++)
  cout<<res[i]<<"\t";
 cout<<endl;
}
/*
*回溯算法
*/
void dfs(int  pos) {
 if(pos>n) {
  //输入结果
  count++;
  show();
  return;
 }
 for(int i=1; i<=n; i++) {
  // 如果数字已经使用或者数字和位置编号相同
  if(vis[i]==1 || i==pos )continue;
  vis[i]=1;
  res[pos]=i;
  //找下一个位置
  dfs(pos+1);
  //回溯
  vis[i]=0;
 }
}
//测试
int main(int argc, char** argv) {
 cin>>n;
 dfs(1);
 cout<<"错排列数："<<count<<endl;
 return 0;
}

测试结果：

广度（BFS）优先搜索法

生成错排列的过程，可认为是从一种原始状态转换到另一种状态的过程。其整个转换过程所有状态所构建成的模型从逻辑上讲一种树结构。回溯算法本质是深度搜索过程，自然，也可以使用广度搜索完成错排列的输出。

现以12345为原始状态，描述对其进行数字交换，改变状态，生成错排列的流程。

把原始状态的最后一位插入到第一位，得到第一个子状态51234（(可定为树结构中的根节点)），此状态也是一种错排列数。如下图：

再在子状态51234的基础上进行状态扩展，得到由此状态转换出的它的子状态。先从第二个位置开始，依次和后面位置中的数字进行交换，交换时，后面位置中与第二位置编号相同的数字不能交换，如第三个位置中的数字2不能交换到第二个位置。再就是第二个位置中的数字不能交换到与此数字相同的位置编号中。如果第二个位置中的数字是4则不能和后面第四个位置中的数字交换。总体原则：数字不能存储至与之相同的下标处。再把第三个位置的数字与后面的位置中的数字交换。以此类推，直到所有位置交换。如下图所示：

依照上述的原则，再在新生成的子状态（即错排列）的基础上重新转换出更多的子状态。一生二、二生三、三生多……直到不能再生成为止。在实际搜索时，需要保证不能回流。

当以子状态51234为始点不停扩展出新节点到不能再扩展时，再生成新的始点45123继续扩展。相当于分别以51234、45123、34512、23451为出发点进行多次的BFS，最终得到所有子状态。

具体实现代码如下：

因为要在数字上进行交换，为了方便可以把数字以字符串的形式存储。这样无论是插入还是交换都能在O(1)时间内完成。从交换逻辑而言，其时间复杂度是常数级别的。

#include <bits/stdc++.h>
using namespace std;
int c=0;
//记录是否访问过
map<string,int> vis;
/*
*由原始字符串生成始状态（树的根节点）
*/
string swapStr(string str) {
 str=str[str.size()-1]+str.substr(0,str.size()-1);
 return str;
}
//广度搜索
void bfs(string str) {
 queue<string> myq;
 int size=str.size();
 string str_=swapStr(str);
 int idx;
 while(str_.compare(str)!=0) {
  myq.push(str_);
  vis[str_]=1;
  idx=0;
  int s=myq.size();
  while( !myq.empty() ) {
   //从队列中拿取所有错排列
   string t= myq.front();
   cout<<t<<endl;
   c++;
   myq.pop();
   string t1=t;
   idx=0;
   //当前位置和其后面位置进行交换
   while(idx<size-1) {
    idx++;
    for( int i1=idx+1; i1<size; i1++ ) {
                    //需要满足2个条件
     if( t1[i1]-'0'!=(idx+1)  &&  t1[idx]-'0'!=(i1+1)  ) {
      swap( t1[idx],t1[i1] );
      if(!vis[t1]) {
       myq.push(t1);
       vis[t1]=1;
      }
      t1=t;
     }
    }
   }
  }
        //重新生成树的根节点
  str_=swapStr(str_);
 }
}
int main() {
    string str;
    cin>>str;
 bi(str);
 cout<<c<<endl;
 return 0;
}

测试结果：输入12345后的运行结果。