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];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void Swap(int &a,int &b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int tmp = a;
a = b;
b = tmp;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void nextPermutation(int *_p,int _n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
//1.从后向前找 查找不符合趋势的
int i = _n-1;
while(i > 0 && _p[i - 1] > _p[i])
--i;
if(i == 0)//已到最后
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(_p[j] > _p[i-1] && _p[j] < _p[k])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
k = j;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Swap(_p[k],_p[i-1]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//3.因为从第一步得【i,n-1】是递减的,故第2步中反转p[k],p[i-1]后要把这个区间反转
for(int j = i,k = _n-1;j < k; ++j,--k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Swap(_p[j],_p[k]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Test()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf(" %d",A[i]);
}
printf("\n");
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int tc;
scanf("%d",&tc);
for(int i = 0; i < tc; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Test();
}
return 0;
}
posted on 2011-01-27 16:50
bennycen 阅读(460)
评论(1) 编辑 收藏 引用