1.生成1–n的排列
思路:先输出1开头的排列(这一步是递归调用),然后输出以2开头二点排列(也是递归调用),接着以3开头的排列,…最后以n开头的排列.
递归函数需要一下参数:
已经确定的前缀序列,以便输出
需要进行全排列的元素集合,以便依此选做第一个元素。
void print_permutation(序列A, 集合S) { if(S.empty()) 输出A; else {按照从小到大的顺序依此考虑S的每个元素v print_permutation(在A的末尾加v后得到的新序列, S-{v}); }
实现代码:
#include<iostream> #include<cstdio> using namespace std; int A[101];//用于存放全排列后的元素 //输出1---n的 全排列 //n:全排列元素的结束位置,cur:当前A序列元素的个数. void print_permutation(int n,int *A,int cur){ if(cur==n){//递归边界 ,输出该次全排列元素 for(int i = 0;i < n; i++){ printf("%d",A[i]); } printf("\n"); }else{ for(int i = 1;i <= n; i++){//枚举所有的可能i int ok = 1; for(int j = 0; j < cur; j++){//判断 i是否已经在 序列A 中出现过了. if(A[j]==i){ ok = 0;//进行标记 } } if(ok){//如果没有出现过,就把i放到A序列的最后一个位置处. A[cur] = i; print_permutation(n,A,cur+1);//继续进行递归调用. 将元素加入A序列. } } } } int main() { int n; scanf("%d",&n); print_permutation(n,A,0); return 0; }
运行结果:
2.生成可重复的排列
问题描述:输入数组P,并按照字典序输出数组A各元素的所有全排列.
P里面的元素可能会有重复的,所有处理时有很多注意点.
对于重复元素,后序该加多少个.如何进行处理
在寻找下一个元素时对于重复元素如何处理.
#include<cstdio> #include<algorithm> using namespace std; int P[100],A[100]; void print_permutation(int n,int *P,int *A,int cur) { if(cur==n) { for(int i = 0; i < n; i++){ printf("%d",A[i]); } printf("\n"); }else { for(int i = 0;i<n;i++){//枚举每一个元素 这里的if是为了排除同一位置重复搞的情况. 不然会出现重复的情况 如:先把第一个1作为开头,再把第二个1作为开头,再把第三个1,作为开头,这样就会导致重复. if(!i||P[i]!=P[i-1]){//==>>去除重复的元素. 由于P数组已经进行过排序了, 在处理时, //当当前元素和前面的元素一致,此种情况便不再进行枚举. int c1 = 0,c2 = 0;//c1,c2的使用是因为 P中会有重复的,所以构成的序列也有多个重复元素. 当 < 时,才进行加入.. for(int j = 0; j<cur;j++){//统计当前元素在A中的个数. if(A[j]==P[i]){ c1++; } } for(int j = 0; j < n; j++){//统计当前元素在P中的个数. if(P[i]==P[j]){ c2++; } } if(c1 < c2){//如果A中的该元素 < P中的该元素,则直接加入A. 因为P中会有重复的,所以构成的序列也有多个重复元素. A[cur] = P[i]; print_permutation(n,P,A,cur+1);//继续递归. } } } } } int main() { int n; scanf("%d",&n); for(int i = 0;i<n;i++){ scanf("%d",&P[i]); } sort(P,P+n); print_permutation(n,P,A,0); return 0; }
运行结果:
3.STL之求下一个序列
STL 为我们提供了next_permutation(),这个可以方便的求枚举排列.
#include<cstdio> #include<algorithm> using namespace std; int main() { int n,p[10]; scanf("%d",&n); for(int i = 0;i <n;i++){ scanf("%d",&p[i]); } sort(p,p+n); do{//这个一般和do...while进行搭配使用. for(int i = 0;i < n;i++){ printf("%d",p[i]);//输出 } printf("\n"); }while(next_permutation(p,p+n)); return 0; }
运行结果:
注:STL还有一个prev_permutaion()可以求上一个序列。
总结:枚举排列的方法有两种:一是递归枚举,二是用STL中的next_permutation().