全排列 dfs

全排列  给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = "1312"， 输出为： 1123 1132 1213 1231 1312 1321 2113 2131 2311 3112 3121 3211 1. 先写一发简单的（直接套用C++标准库中提供的next_permutation函数，将n个元素共n!种不同的排列生成出来） #include<iostream> #include<algorithm> #include<cstring> using namespace std; char s[12]; int a[12]={0}; int len; void input() { cin>>s; len=strlen(s); for(int i=0;i<len;i++) //将字符串中的数字找出来放入a中 a[i]=(int)(s[i]-'0'); sort(a,a+len); //排序 } int main() { input(); do { for(int i=0;i<len;i++) cout<<a[i]; cout<<endl; }while(next_permutation(a,a+len)); return 0; } 2. dfs的简单应用，可以拿来练习dfs  思路：把数存储在数组a中，不断放入数组b中形成全排列，再将b输出即可。 比如有123, a[0]=1,a[1]=2,a[2]=3, 放入b中：        第一种: 将1放入b中，即b[0]=1, 依次有 b[1]=2, b[2]=3，此时b的长度和a的长度相等也就是b已经放满，可以将此结果输出   第二种: 在第一种回退（回溯），b[0]=1,b[1]=2,b[2]清除，但此时3还是只能放在b[2]，所以只能继续回溯，将b[2]清除               b[0]=1,b[1]=3,b[2]=2,这是第二种情况   第三种: 在第二种基础上回溯，直到回溯到b[0] ，得出b[0]=2,b[1]=1,b[2]=3（因为要求是字典序，故数值小的数优先放在前面）   ......（依次类推） #include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[12]; int b[12]; int vis[12]; char s[12]; int len; void dfs(int s) { if(s==len) { for(int i=0;i<len;i++) cout<<b[i]; cout<<endl; return; } else { for(int i=0;i<len;i++) { if(!vis[i]) { vis[i]=1; b[s]=a[i]; dfs(s+1); vis[i]=0; //回溯 将已经标记访问过的标记清除 while(a[i]==a[i+1]) i++; //去重 （比如有三个1，三个1无所谓谁前谁后） } } } } int main() { cin>>s; memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); len=strlen(s); for(int i=0;i<len;i++) a[i]=(int)(s[i]-'0'); sort(a,a+len); //排序 dfs(0); return 0; }