百度面试题——需找下一个排列(Find next permuation, POJ 1883)

面试中关于排列的题目还是蛮常见的，之前有个同学面百度，就遇到了一个排列题目，分享一下。

题目描述：
给你一个数组，如果是按照数字的大小排序，那么请你输出当前数组的下一个排列是什么

例如， 下面的数据，就是按照排列序生成的四组数据。

3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2

虽然有个函数叫next_permutation, 不过做OJ还好，面试这个一定不行啦，所以还是自己分析一下。

分析：
我们用字典序的排列生成方法：

生成给定全排列的下一个排列

所谓一个的下一个就是这一个与

下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

 算法分三个步骤：

一般而言，设P是[1,n]的一个全排列。

1.  P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn

j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}

2.  对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，

3. P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个。

代码如下：

1. Memory: 168K        Time: 469MS 
2. Language: C++       Result: Accepted 
3. Source Code 
4. #include<stdio.h>  
5. #include <memory.h>  
6.  
7. void swap( int &a, int &b) 
8. { 
9.     a = a ^ b; 
10.     b = a ^ b; 
11.     a = a ^ b; 
12. } 
13.  
14.  
15. bool GetNextPermutation(int a[], int size) 
16. { 
17.     int m = size – 1; 
18.     int i,j; 
19.     while(m > 0 && a[m-1] > a[m]) // step 1  
20.     { 
21.         m–; 
22.     } 
23.  
24.     //in this case, the current permutation is the last  
25.     if(m == 0) //  
26.     { 
27.         for( i = 0, j = size – 1; i < j; i++, j–) 
28.         { 
29.             swap(a[i], a[j]); 
30.         } 
31.         return false; 
32.     } 
33.  
34.     for( j = size – 1; j > m – 1; j–)//step 2  
35.     { 
36.         if(a[j] > a[m-1]) 
37.         { 
38.             swap(a[j], a[m-1]); 
39.             break; 
40.         } 
41.     } 
42.  
43.     for( i = m, j = size – 1; i < j; i++, j–)//step 3  
44.     { 
45.         swap(a[j], a[i]); 
46.     } 
47.     return true; 
48. } 
49.  
50. void printArray(int a[], int size) 
51. { 
52.     int i; 
53.  
54.     for( i = 0; i < size; i++) 
55.     {   
56.         if( i == 0) 
57.         { 
58.             printf(“%d”, a[i]); 
59.         } 
60.         else 
61.         { 
62.             printf(” %d”, a[i]); 
63.  
64.         } 
65.     } 
66.     printf(“\n”); 
67. } 
68. int main() 
69. { 
70.     int nSize; 
71.     int a[1024]; 
72.     int ncase; 
73.  
74.     scanf(“%d”, &ncase); 
75.     int n,k; 
76.     while(ncase–) 
77.     { 
78.         scanf(“%d%d”, &n, &k); 
79.  
80.         for( int i = 0; i < n; i++) 
81.         { 
82.             scanf(“%d”, &a[i]); 
83.         } 
84.  
85.         while(k–) 
86.         { 
87.             GetNextPermutation(a, n); 
88.              
89.         } 
90.         printArray(a, n); 
91.      
92.     } 
93.     return 0; 
94. } 

不过既然提到求出排练顺便再给出一个生成所有排列的方法。就是组合数学里面说的“交换法”

这个方法运行的流程如下： 

考虑{1,2…n}的一个排列，其上每一个整数都给了一个方向，我们称整数k是可移的(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如

中6、3、5都是可移的。显然1永远不可移，n除了以下两种情形外，它都是可移的:

(1) n是第一个数，且其方向指向左侧

(2) n是最后一个数，且其方向指向右侧

于是，我们可由

按如下算法产生所有排列

算法

1，开始时：

2，当存在可移数时

(a)找最大的可移数m
(b)将m与其箭头所指的邻数互换位置
(c)将所得排列中比m大的数p的方向调整，即改为相反方向。
 
代码如下：

1. #include <stdio.h>  
2. #include <memory.h>  
3.  
4. enum Direction{LEFT, RIGHT}; //方向枚举  
5.  
6.  
7. struct Num //每个数有一个方向和值  
8. { 
9.     Direction d; 
10.     int value; 
11. };   
12.  
13. Num permutation[100]; 
14.  
15. //if return value is -1, it means we can’t find the permutation anymore  
16. int GetFirstMoveable(int nsize) //在所有数里面找到最大的可以移动的数，返回下标  
17. { 
18.     int maxValue = 0; 
19.     int idx = -1; 
20.     for( int i = 0;i < nsize; i++) 
21.     { 
22.         if( i == 0 && permutation[i].d == LEFT)//最左边，并且移动方向是左  
23.         { 
24.             continue; 
25.         } 
26.         if( i == nsize – 1 && permutation[i].d == RIGHT)//最右边，并且移动方向向右  
27.         { 
28.             continue; 
29.         }   
30.         if(permutation[i].d == LEFT)//如果方向是左，并且比左侧元素大  
31.         { 
32.             if(permutation[i].value > permutation[i-1].value) 
33.             { 
34.                 if(maxValue < permutation[i].value) 
35.                 { 
36.                     maxValue = permutation[i].value; 
37.                     idx = i; 
38.                 } 
39.             } 
40.         } 
41.         else   
42.         { 
43.             if(permutation[i].value > permutation[i+1].value)//方向向右，比右侧大  
44.             { 
45.                 if(maxValue < permutation[i].value) 
46.                 { 
47.                     maxValue = permutation[i].value; 
48.                     idx = i; 
49.                 } 
50.             } 
51.         } 
52.     } 
53.     return idx; 
54. } 
55.  
56. void reverseDirection(int r, int nsize) //交换完了以后，将所有大于当前交换的值的 方向调反  
57. { 
58.     for( int i = 0; i < nsize; i++) 
59.     { 
60.         if(permutation[i].value > permutation[r].value) 
61.         { 
62.             if(permutation[i].d == LEFT) 
63.             { 
64.                 permutation[i].d = RIGHT; 
65.             } 
66.             else 
67.             { 
68.                 permutation[i].d = LEFT; 
69.             } 
70.         } 
71.     } 
72.  
73. } 
74. void swap(Num & a, Num & b) 
75. { 
76.     Num t = a; 
77.     a = b; 
78.     b = t; 
79. } 
80. void swapValue(int r, int &nr)//交换相邻的值  
81. { 
82.  
83.     if(permutation[r].d == LEFT) 
84.     { 
85.         swap(permutation[r], permutation[r-1]); 
86.         nr = r – 1; 
87.     } 
88.     else 
89.     { 
90.         swap(permutation[r], permutation[r+1]); 
91.         nr = r + 1; 
92.     } 
93.  
94. } 
95.  
96. void printAll(int nsize) 
97. { 
98.     for(int i = 0; i < nsize; i++) 
99.     { 
100.         printf(“%d “, permutation[i].value ); 
101.     } 
102.     printf(“\n”); 
103. } 
104. int main() 
105. { 
106.     int n; 
107.  
108.     while(scanf(“%d”,&n) != EOF) 
109.     { 
110.         for( int i = 0; i < n;i++) 
111.         { 
112.             permutation[i].value = i + 1; 
113.             permutation[i].d = LEFT; 
114.         } 
115.         int r;   
116.         int nr; 
117.         printAll(n); 
118.         while( (r = GetFirstMoveable(n)) != -1)//算法核心循环  
119.         { 
120.             swapValue(r, nr); 
121.             reverseDirection(nr, n); 
122.             printAll(n); 
123.  
124.  
125.         } 
126.     } 
127.     return 0; 
128. }