一文看懂全排列算法!

一文看懂全排列算法!

作者 | Cooper Song

责编 | 伍杏玲

出品 | CSDN (ID:CSDNnews)

所谓全排列,就是把一堆字符按照一定的顺序排列起来,所有可能的组合。举个简单的例子,"123" 的全排列为 "123"、"132"、"213"、"231"、"312"、"321"。

一文看懂全排列算法!

使用库函数进行全排列

C++的头文件中实现了全排列,即 next_permutation 函数,它是基于字典序实现的,执行一次 next_permutation 函数就相当于进行了一次“变异”,变异之后字典序会比原来的字符串大,但其位次也仅仅排在变异之前的字符串之后。什么意思呢?比如 "123" 调用 next_permutation 函数经过一次变异之后会变成 "132",而不是 "213"、"321" 等字典序更大的字符串。next_permutation 是有返回值的,返回值为 true 或 false,意思是如果变异之后仍然产生了新的排列就会返回 true,不能再产生新的排列了就会返回 false。还是上面那个例子,如果当前字符串已经是 "321" 了,不存在字典序比 "321" 更大的排列了,此时就会返回 false。因此,如果要进行全排列的字符串是 "132",就应当先对其排序变成 "123",否则在全排列时就会漏掉 "123"。

next_permutation 的用法如下:

    #include       #include       using namespace std;      string str;      int main()      {          getline(cin,str);          // 先进行排序使之字典序最小          sort(str.begin(),str.end());          cout<<" 其全排列为 :"<<endl;          do          {              cout<endl;          }while(next_permutation(str.begin(),str.end()));          return 0;      }

一文看懂全排列算法!

一文看懂全排列算法!

手撕全排列

可是如何用编程实现这一过程呢?本文就教大家使用深搜回溯算法实现全排列。代码如下:

    #include       #include       #include       using namespace std;      string str;      string temp;      vector<bool> vis;      void dfs(int cnt,int n)      {          if(cnt==n)          {              cout<endl;              return;          }          for(int i=0;i    {              if(vis[i]==false)              {                  temp.push_back(str[i]);                  vis[i]=true;                  dfs(cnt+1,n);                  vis[i]=false;                  temp.pop_back();              }          }      }      int main()      {          getline(cin,str);          sort(str.begin(),str.end());          int n=str.size();          vis.resize(n);          dfs(0,n);          return 0;      }

我们把产生的排练暂存在字符串 temp 中,当 temp 中的字符个数与初始字符串的字符个数相等时就将 temp 输出了。

数组 vis 存放的是字符串的某个下标索引到的字符有没有加入 temp,如果加入了 temp 就将其 vis 置为 true,没加入的其 vis 就为 false。dfs 传入的参数 cnt 是指已经填入 temp 的字符个数,n 是初始字符串的字符个数。有了上面那些铺垫,我们在主函数中调用 dfs(0,n),意思是初始状态 temp 中没有字符。为了建立字符与下标之间的联系,方便大家观察,我们使用 "012" 这个例子描述算法,最初 temp={},vis 都为 false,进了递归函数 dfs,就开始遍历初始字符串,依次往 temp 填入字符。在阅读下面的过程之前,我邀请大家关注两个要素,递归层数和当前递归层数下 i 的值,这两个要素直接决定了下一个要尝试填入的字符。起初递归层数为 0。从 i=0 开始遍历。i=0 时,vis[0]=false,将 0 填入 temp,然后将 vis[0] 置为 true,传入 cnt+1=1 表示 temp 中已有字符的个数为 1,进行下一层递归,此时temp={0}此时递归层数为 1。从 i=0 开始遍历。i=0 时,vis[0]=true,0 已经被填入 temp 了不满足条件;i=1 时,vis[1]=false,将 1 填入 temp,然后将 vis[1] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={0,1}此时递归层数为 2。从 i=0 开始遍历。i=0 时,vis[0]=true,0 已经被填入 temp 了不满足条件;i=1 时,vis[1]=true,1 已经被填入 temp 了不满足条件;i=2 时,vis[2]=false,将 2 填入 temp,然后将 vis[2] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={0,1,2}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=2 了,从 dfs 返回后取出 temp 末尾的字符 2,于是将 vis[2] 又置为了 false,继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时temp={0,1}此时递归层数为 1。上次在 1 层递归里遍历到 i=1 了,从 dfs 返回后取出 temp 末尾的字符 1,于是将 vis[1] 又置为了 false;此时temp={0}继续遍历,此时 i=2,vis[2]=false,将 2 填入 temp,然后将 vis[2] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={0,2}此时递归层数为 2。i=0 时,vis[0]=true,0 已经被填入 temp 了不满足条件;i=1 时,vis[1]=false,将 1 填入 temp,然后将 vis[1] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={0,2,1}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=1 了,从 dfs 返回后取出 temp 末尾的字符 1,于是将 vis[1] 又置为了 false。此时temp={0,2}继续遍历,此时 i=2,vis[2]=true,2 已经被填入 temp 了不满足条件;继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时递归层数为 1。上次在 1 层递归里遍历到 i=2 了,从 dfs 返回后取出 temp 末尾的字符 2,于是将 vis[2] 又置为了 false。此时temp={0}继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时递归层数为 0。上次在 0 层递归里遍历到 i=0 了,从 dfs 返回后取出 temp 末尾的字符 0,于是将 vis[0] 又置为了 false。此时temp={}继续遍历,此时 i=1,vis[1]=false,将 1 填入 temp,并将 vis[1] 置为 true,传入 cnt+1=1 表示 temp 中已有字符的个数为 1,进行下一层递归,此时temp={1}此时递归层数为 1。从 i=0 开始遍历。i=0 时,vis[0]=false,将 0 填入 temp,然后将 vis[0] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={1,0}此时递归层数为 2。从 i=0 开始遍历。i=0 时,vis[0]=true,0 已经被填入 temp 了不满足条件;i=1 时,vis[1]=true,1 已经被填入 temp 了不满足条件;i=2 时,vis[2]=false,将 2 填入 temp,然后将 vis[2] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={1,0,2}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=2 了,从 dfs 返回后取出 temp 末尾的字符 2,于是将 vis[2] 又置为了 false;继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时temp={1,0}此时递归层数为 1。上次在 1 层递归里遍历到 i=0 了,从 dfs 返回后取出 temp 末尾的字符 0,于是将 vis[0] 又置为了 false;此时temp={1}继续遍历,此时 i=1,vis[1]=true,1 已经被填入 temp 了不满足条件;继续遍历,此时 i=2,vis[2]=false,将 2 填入 temp,然后将 vis[2] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={1,2}此时递归层数为 2。从 i=0 开始遍历。i=0 时,vis[0]=false,将 0 填入 temp,然后将 vis[0] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={1,2,0}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=0 了,从 dfs 返回后取出 temp 末尾的字符,其实就是 0,于是将 vis[0] 又置为了 false;继续遍历,vis[1] 和 vis[2] 都为 true,也就是 1 和 2 都在 temp 里,都不满足条件,遍历结束返回上一层递归。此时temp={1,2}此时递归层数为 1。上次在 1 层递归里遍历到 i=2 了,从 dfs 返回后取出 temp 末尾的字符 2,于是将 vis[2] 又置为了 false;此时temp={1}继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时此时递归层数为 0。上次在 0 层递归里遍历到 i=1 了,从 dfs 返回后取出 temp 末尾的字符 1,于是将 vis[1] 又置为了 false;此时temp={}继续遍历,此时 i=2,vis[2]=false,将 2 填入 temp,然后将 vis[2] 置为 true,传入 cnt+1=1 表示 temp 中已有字符的个数为 1,进行下一层递归,此时temp={2}此时递归层数为 1。从 i=0 开始遍历。i=0 时,vis[0]=false,将 0 填入 temp,然后将 vis[0] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={2,0}此时递归层数为 2。从 i=0 开始遍历。i=0 时,vis[0]=true,0 已经被填入 temp 了不满足条件;i=1 时,vis[1]=false,将 1 填入 temp,然后将 vis[1] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={2,0,1}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=1 了,从 dfs 返回后取出 temp 末尾的字符 1,于是将 vis[1] 又置为了 false;此时temp={2,0}继续遍历,此时 i=2,vis[2]=true,2 已经被填入 temp 了不满足条件;继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时递归层数为 1。上次在 1 层递归里遍历到 i=0 了,从 dfs 返回后取出 temp 末尾的字符 0,于是将 vis[0] 又置为了 false;此时temp={2}继续遍历,此时 i=1,vis[1]=false,将 1 填入 temp,然后将 vis[1] 置为 true,传入 cnt+1=2 表示 temp 中已有字符的个数为 2,进行下一层递归,此时temp={2,1}此时递归层数为 2。从 i=0 开始遍历。i=0 时,vis[0]=false,将 0 填入 temp,然后将 vis[0] 置为 true,传入 cnt+1=3 表示 temp 中已有字符的个数为 3,进行下一层递归,此时temp={2,1,0}此时递归层数为 3。经判断 temp 中已经填入了 3 个字符,达到了“出厂要求”,将其输出后返回上一层递归。此时递归层数为 2。上次在 2 层递归里遍历到 i=0 了,从 dfs 返回后取出 temp 末尾的字符 0,于是将 vis[0] 又置为了 false;此时temp={2,1}继续遍历,vis[1] 和 vis[2] 都为 true,意味着 1 和 2 都在 temp 里,都不满足条件,遍历结束,返回上一层递归。此时递归层数为 1。上次在 1 层递归里遍历到 i=1 了,从 dfs 返回后取出 temp 末尾的字符 1,于是将 vis[1] 又置为了 false;此时temp={2}继续遍历,此时 i=2,vis[2]=true,2 已经被填入 temp 了不满足条件;继续遍历,i=3 超出了下标范围,遍历结束,返回上一层递归。此时递归层数为 0。上次在 0 层递归里遍历到 i=2 了,从 dfs 返回后取出 temp 末尾的字符 2,于是将 vis[2] 又置为了 false。此时temp={}继续遍历,i=3 超出了下标范围,遍历结束。全排列到此结束,temp 和 vis 都恢复了最初的状态。又到了金三银四面试季,衷心祝愿大家都能拿到想要的 Offer。

【End】

一文看懂全排列算法!推荐阅读面对疫情等群体性危机,程序员如何在家高效办公?特殊时期,字节跳动高效有序的远程协作办公经验,值得各企业学习!你离成为优秀的架构师,就差这份超全路线图了
AAAI 2020 论文解读:商汤科技提出新弱监督目标检测框架GitHub 标星 14000+,阿里开源的 SEATA 如何应用到极致?区块链创业的尴与尬一文看懂全排列算法!你点的每一个在看,我认真当成了喜欢