STL有一个函数叫next_ermutation,是得出当前排列的下一个排列，数列P[0..n-1](P[i] > P[j]当n>i>j>=0)为最小的排列，然后按照一般数字的排列比较进行排列，就是说该排列的下一个排列比这个排列大，最后的当然是P*[0..n-1](P*[i] < P*[j]当n>i>j>=0)
例如 1 2 3 4，最小的是1 2 3 4，下一个是1 2 4 3.。。。最大是4 3 2 1了。
怎么得出当前排列的下一个排列呢？
定义n为数组P【0,n-1】的长度
下面要考虑的问题，是如何从一个已知的排列P = p
1p
2…p
n，找到它的下一个排列
Q = q
1q
2…q
n。我们要让排列从小到大生成，简单说，要让排列的趋势从P[0..n-1](P[i] > P[j]当n>i>j>=0)到P*[0..n-1](P*[i] < P*[j]当n>i>j>=0)。
我们可以结合十进制的大小比较来理解。以下以1 3 4 2为例子来说
1.首先从低位找起，找出比高位大的第一个数的位置，定义i为这个位置。(想一下就知道了)若找不到这样的P[i]，说明我们已经找到最后一个全排列，可以返回了。
1 3 4 2 --> 4比3 大，这个位置是第2位(1为第0位，3 为第1位)，这时 i = 2
2.再在区间[i,n-1]中查找比P[i-1]大的最小的数。
这个也很容易理解，从例子中看出，这个最小的数是4
然后交换两者，那么现在的数组是1 4 3 2
3.现在还不是最小的数，因为从第一步的查找，我们有P[i]>P[i+1]> … >P[n-1]，否则查找在i～n就会停下来了。这样的一个排列显然不是最小的。实际上，原来的P[i...n-1]，已经是这一部分最大的一个排列了。但我们现在换了最高位P[i-1]，因此要让后面的数字变的最小。方法很简单，根据上面的推理，我们只须将P[i...n-1]的数列倒置即可（最大的排列倒置就变成了最小的排列）。
回到例子，1 4 3 2 --> 14 2 3得到答案
看完了分析，现在做一题OJ题目
POJ 题目
http://poj.org/problem?id=1833解答
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[1200];
inline void Swap(int &a,int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void nextPermutation(int *_p,int _n)
{
//1.从后向前找 查找不符合趋势的
int i = _n-1;
while(i > 0 && _p[i - 1] > _p[i])
--i;
if(i == 0)//已到最后
{
sort(_p,_p+_n);
return ;
}
//2.查找【i,n-1】中大于p[i-1]的最小数
int k = i;//p[i]必大于p[i-1]
for(int j = i; j <= _n-1; ++j)
{
if(_p[j] > _p[i-1] && _p[j] < _p[k])
{
k = j;
}
}
Swap(_p[k],_p[i-1]);
//3.因为从第一步得【i,n-1】是递减的，故第2步中反转p[k],p[i-1]后要把这个区间反转
for(int j = i,k = _n-1;j < k; ++j,--k)
{
Swap(_p[j],_p[k]);
}
}
void Test()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 0; i < n; ++i)
scanf("%d",&A[i]);
for(int i = 0; i < m ; ++i)
nextPermutation(A,n);
printf("%d",A[0]);
for(int i = 1; i < n; ++i)
{
printf(" %d",A[i]);
}
printf("\n");
}
int main()
{
int tc;
scanf("%d",&tc);
for(int i = 0; i < tc; ++i)
{
Test();
}
return 0;
}posted on 2011-01-27 16:50
bennycen 阅读(470)
评论(1) 编辑 收藏 引用