posts - 33,  comments - 33,  trackbacks - 0
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 = p1p2…pn,找到它的下一个排列
Q = q1q2…qn。我们要让排列从小到大生成,简单说,要让排列的趋势从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 阅读(450) 评论(1)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理