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

2012-09-06

百度面试题——需找下一个排列(Find next permuation, POJ 1883)面试中关于排列的题目还是蛮常见的，之前有个

百度面试题——需找下一个排列(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

百度一下发现POJ上居然有一个一模一样题目： http://poj.org/problem?id=1833.

虽然有个函数叫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的下一个。

代码如下：


  
中6、3、5都是可移的。显然1永远不可移，n除了以下两种情形外，它都是可移的:
(1) n是第一个数，且其方向指向左侧
(2) n是最后一个数，且其方向指向右侧
于是，我们可由
按如下算法产生所有排列
算法
1，开始时：

2，当存在可移数时
(a)找最大的可移数m(b)将m与其箭头所指的邻数互换位置(c)将所得排列中比m大的数p的方向调整，即改为相反方向。
代码如下：#include <stdio.h>#include <memory.h>enum Direction{LEFT, RIGHT}; //方向枚举struct Num //每个数有一个方向和值{Direction d;int value;}; Num permutation[100];//if return value is -1, it means we can't find the permutation anymoreint GetFirstMoveable(int nsize) //在所有数里面找到最大的可以移动的数，返回下标{int maxValue = 0;int idx = -1;for( int i = 0;i < nsize; i++){if( i == 0 && permutation[i].d == LEFT)//最左边，并且移动方向是左{continue;}if( i == nsize - 1 && permutation[i].d == RIGHT)//最右边，并且移动方向向右{continue;} if(permutation[i].d == LEFT)//如果方向是左，并且比左侧元素大{if(permutation[i].value > permutation[i-1].value){if(maxValue < permutation[i].value){maxValue = permutation[i].value;idx = i;}}}else {if(permutation[i].value > permutation[i+1].value)//方向向右，比右侧大{if(maxValue < permutation[i].value){maxValue = permutation[i].value;idx = i;}}}}return idx;}void reverseDirection(int r, int nsize) //交换完了以后，将所有大于当前交换的值的 方向调反{for( int i = 0; i < nsize; i++){if(permutation[i].value > permutation[r].value){if(permutation[i].d == LEFT){permutation[i].d = RIGHT;}else{permutation[i].d = LEFT;}}}}void swap(Num & a, Num & b){Num t = a;a = b;b = t;}void swapValue(int r, int &nr)//交换相邻的值{if(permutation[r].d == LEFT){swap(permutation[r], permutation[r-1]);nr = r - 1;}else{swap(permutation[r], permutation[r+1]);nr = r + 1;}}void printAll(int nsize){for(int i = 0; i < nsize; i++){printf("%d ", permutation[i].value );}printf("\n");}int main(){int n;while(scanf("%d",&n) != EOF){for( int i = 0; i < n;i++){permutation[i].value = i + 1;permutation[i].d = LEFT;}int r; int nr;printAll(n);while( (r = GetFirstMoveable(n)) != -1)//算法核心循环{swapValue(r, nr);reverseDirection(nr, n);printAll(n);}}return 0;}

热点排行

编程

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