百度面試題——需找下一個排列(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. }