百度面試題——需找下一個排列(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>
7. void swap( int &a, int &b)
8. {
9. a = a ^ b;
10. b = a ^ b;
11. a = a ^ b;
12. }
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. }
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. }
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. }
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. }
50. void printArray(int a[], int size)
51. {
52. int i;
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]);
64. }
65. }
66. printf("\n");
67. }
68. int main()
69. {
70. int nSize;
71. int a[1024];
72. int ncase;
74. scanf("%d", &ncase);
75. int n,k;
76. while(ncase--)
77. {
78. scanf("%d%d", &n, &k);
80. for( int i = 0; i < n; i++)
81. {
82. scanf("%d", &a[i]);
83. }
85. while(k--)
86. {
87. GetNextPermutation(a, n);
89. }
90. printArray(a, n);
92. }
93. return 0;
94. }