百度面试题——需找下一个排列(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  Language: C++       Result: Accepted 
2. Source Code  #include<stdio.h>  
3. #include <memory.h>    
4. void swap( int &a, int &b)  { 
5.     a = a ^ b;      b = a ^ b; 
6.     a = a ^ b;  } 
7.    
8. bool GetNextPermutation(int a[], int size)  { 
9.     int m = size - 1;      int i,j; 
10.     while(m > 0 && a[m-1] > a[m]) // step 1       { 
11.         m--;      } 
12.       //in this case, the current permutation is the last  
13.     if(m == 0) //       { 
14.         for( i = 0, j = size - 1; i < j; i++, j--)          { 
15.             swap(a[i], a[j]);          } 
16.         return false;      } 
17.       for( j = size - 1; j > m - 1; j--)//step 2  
18.     {          if(a[j] > a[m-1]) 
19.         {              swap(a[j], a[m-1]); 
20.             break;          } 
21.     }   
22.     for( i = m, j = size - 1; i < j; i++, j--)//step 3       { 
23.         swap(a[j], a[i]);      } 
24.     return true;  } 
25.   void printArray(int a[], int size) 
26. {      int i; 
27.       for( i = 0; i < size; i++) 
28.     {            if( i == 0) 
29.         {              printf("%d", a[i]); 
30.         }          else 
31.         {              printf(" %d", a[i]); 
32.           } 
33.     }      printf("\n"); 
34. }  int main() 
35. {      int nSize; 
36.     int a[1024];      int ncase; 
37.       scanf("%d", &ncase); 
38.     int n,k;      while(ncase--) 
39.     {          scanf("%d%d", &n, &k); 
40.           for( int i = 0; i < n; i++) 
41.         {              scanf("%d", &a[i]); 
42.         }   
43.         while(k--)          { 
44.             GetNextPermutation(a, n);               
45.         }          printArray(a, n); 
46.           } 
47.     return 0;  }