首页 > 代码库 > 字典序全排列

字典序全排列

2024-07-04 12:12:17   233人阅读

给出正整数n，则1~n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1 这6个排列。 

字典序算法如下：

假设这n个数的某一个排列为 P: P1 P2 P3...Pj-1 Pj Pj+1...Pk-1 Pk Pk+1...Pn

1.从该序列的最右端开始向左找出第一个比与自己相邻的右边数小的数，记其下标为j，即j = max{i|Pi<pi+1}.

2.找出Pj右边比Pj大的最小数Pk.

3.交换Pj,Pk.此时序列变为 P’: P1 P2 P3...Pj-1 Pk Pj+1...Pk-1 Pj Pk+1...Pn

4.将Pj+1...Pn 倒转，即得到此序列的后一个序列 P”: P1 P2 P3...Pj-1 Pn...Pk+1 Pj Pk-1...Pj+1

例：

1 2 3 5 7 4 6 10 9 8为1-10的一个排列

1.从该序列的最右端开始向左找出第一个比与自己相邻的右边数小的数6，其下标为7

2.6右边比6大的最小数为8

3.交换6,8得到1 2 3 5 7 4 8 10 9 6

4.将P8-P10倒转得到：1 2 3 5 7 4 8 6 9 10即为下一个序列

代码实现：

 1 //对1-n的某个已知排列求按字典序其后的第s个排列
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N = 1030;
 6 //将数组下标a-b的元素翻转
 7 void Flip(int n[],int a,int b){
 8  for(int i = a,j = b; i < j; i ++, j --){
 9      swap(n[i],n[j]);
10  }
11 }
12 //求第k个排列
13 void order(int n,int a[],int s){
14      int j,k,min = n+1,flag = 1;
15  while(s --){
16    for(int i = n-1; i >= 1; i --){
17      if(a[i] < a[i+1]){
18           flag = 0;
19           j = i;
20           break;
21      }
22    }
23    if(flag){
24      for(int i = 1; i <= n; i ++){//排列为n n-1...2 1
25           a[i] = i;
26      }
27    }
28    else{
29      for(int i = j+1; i <= n; i ++){
30           if(a[i] > a[j]){
31                if(a[i] < min){
32                     min = a[i];
33                     k = i;
34                }
35 
36           }
37       }
38       swap(a[j],a[k]);
39       Flip(a,j+1,n);
40    }
41 
42   }
43 
44 }
45 int main(){
46    int m,n,k,num[N];;
47    scanf("%d",&m);
48    while(m --){
49      scanf("%d%d",&n,&k);
50      for(int i = 1; i <= n; i ++){
51           scanf("%d",&num[i]);
52      }
53      order(n,num,k);
54      for(int i = 1; i <= n; i ++){
55           printf(i == 1?"%d":" %d",num[i]);
56      }
57      printf("\n");
58    }
59 return 0;
60 }

另外表示可以用c++ STL中的next_permutation函数生成全排列。。

链接：http://www.cnblogs.com/TonyNeal/archive/2013/05/11/next_permutation.html


联系
我们