江苏龙网

  1. 主页 > 生活百科 > >

一文看懂全排列算法

全排列算法


一文看懂全排列算法

文章插图
作者 | Cooper Song
责编 | 伍杏玲
所谓全排列 ， 就是把一堆字符按照一定的顺序排列起来 ， 所有可能的组合 。
举个简单的例子 ， "123"的全排列为"123"、"132"、"213"、"231"、"312"、"321" 。
1.使用库函数进行全排列C++的<algorithm>头文件中实现了全排列 ， 即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 <IOStream>
#include <algorithm>
using namespace std;
string str;
int main
{
getline(cin,str);
//先进行排序使之字典序最小
sort(str.begin,str.end);
cout<<"其全排列为:"<<endl;
do
{
cout<<str<<endl;
}while(next_permutation(str.begin,str.end));
return 0;
}
一文看懂全排列算法

文章插图
2.手撕全排列可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列 。代码如下：
#include <iostream>#include <vector>#include <algorithm>using namespace std;string str;string temp;vector<bool> vis;void dfs(int cnt,int n){if(cnt==n){cout<<temp<<endl;return;}for(int i=0;i<n;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 ， 进行下一层递归 ， 此时


推荐阅读


上一篇：CentOS系统如何禁止root用户登录

下一篇：怎么防止黑衣服粘白毛 白衣服粘毛干了会掉吗