1.六个数里取所有三个数的全排列按字典序输出
法一：我记得比赛时我用的是二维数组，每一维先排序，竟然立马水过了，后来我想要是数多了就很麻烦，于是有了下面的方法。
法二：
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 25; 7 int n,num; 8 int a[maxn]; 9 bool vis[maxn] = {false}; 10 11 void fun(int cnt) 12 { 13 if(cnt==num) 14 { 15 cout<<a[0]; 16 //若是判断给一个排列求出它是第几个 那么就在这判断吧 17 for(int i=1; i<num; i++) 18 cout<<" "<<a[i]; 19 cout<<endl; 20 return ; 21 } 22 else 23 for(int i=1; i<=n; i++) 24 if(!vis[i]) 25 { 26 vis[i] = true; 27 a[cnt] = i; 28 fun(cnt+1); 29 vis[i] = false; 30 } 31 } 32 33 int main() 34 { 35 int i,j,k; 36 37 cin>>n>>num; 38 fun(0); 39 system("pause"); 40 return 0; 41 }
2.求字典序的第k的排列
参见POJ 1037(不只是简单地求第几个排列),下面的方法都超时（应该是WA）了;参加黑书P257,也可以求1开头的共几个排列，这样逼近，不过若是位数较多，数组开不了
法一：
1 //超时，求第几个排列 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 25; 8 int n,k; 9 int a[maxn]; 10 11 void solve() 12 { 13 int cnt = 0; 14 do 15 { 16 cnt++; 17 if(k==cnt) 18 { 19 cout<<a[0]; 20 for(int i=1; i<n; i++) 21 cout<<" "<<a[i]; 22 cout<<endl; 23 break; 24 } 25 26 }while(next_permutation(a,a+n)); 27 } 28 29 int main() 30 { 31 int i,j; 32 int T; 33 cin>>T; 34 while(T--) 35 { 36 37 cin>>n>>k; 38 for(int i=0; i<n; i++) 39 a[i] = i+ 1; 40 solve(); 41 } 42 return 0; 43 }
法二：
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 25; 7 int n,k; 8 int a[maxn]; 9 int cnt = 0; 10 11 void solve(int cur) 12 { 13 if(cur==n) 14 { 15 cnt++; 16 if(cnt==k) 17 { 18 cout<<a[0]; 19 for(int i=1; i<n; i++) 20 cout<<" "<<a[i]; 21 cout<<endl; 22 return ; 23 } 24 } 25 else 26 for(int i=1; i<=n; i++) 27 { 28 bool ok = true; 29 for(int j=0; j<cur; j++) 30 if(a[j]==i) 31 ok = false; 32 if(ok) 33 { 34 a[cur] = i; 35 solve(cur+1); 36 } 37 } 38 } 39 40 41 int main() 42 { 43 int i,j; 44 int T; 45 cin>>T; 46 while(T--) 47 { 48 cnt = 0; 49 cin>>n>>k; 50 solve(0); 51 } 52 return 0; 53 }
3.求上一个和下一个排列
一.上一个排列
普通算法没找到，可以直接prev_permutation()
二.下一个排列
a.普通算法
从最后一位 找到第一个非递减的位数，假设最末尾连续的递减位数为k;例如12354 54是递减的 所以找到3 k=2;然后将这一位与最后一位互换 例如12354 换成12453;那后k位是降序序的 ;所以将最后k位改成升序即可。
b.
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 int main() 6 { 7 char a[7]="123456"; 8 next_permutation(a,a+6); 9 cout<<a<<endl; 10 system("pause"); 11 return 0; 12 }
