排列组合算法
作者 | Cooper Song
责编 | 伍杏玲
出品 | CSDN（ID：CSDNnews）
所谓全排列，就是把一堆字符按照一定的顺序排列起来，所有可能的组合。举个简单的例子，”123″的全排列为”123″、”132″、”213″、”231″、”312″、”321″。
使用库函数进行全排列
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()
{
cin,str);
//先进行排序使之字典序最小
cout<<“其全排列为:”<<endl;
do
cout<<str<<endl;
while(next_permutation(str.begin(),str.end()));
return 0;
手撕全排列
可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列。代码如下：#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]);
true;
1,n);
false;
}
}
int main()
{
cin,str);
int n=str.size();
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 如何应用到极致？?区块链创业的尴与尬你点的每一个在看，我认真当成了喜欢