STL有一個(gè)函數(shù)叫next_ermutation,是得出當(dāng)前排列的下一個(gè)排列，數(shù)列P[0..n-1](P[i] > P[j]當(dāng)n>i>j>=0)為最小的排列，然后按照一般數(shù)字的排列比較進(jìn)行排列，就是說該排列的下一個(gè)排列比這個(gè)排列大，最后的當(dāng)然是P*[0..n-1](P*[i] < P*[j]當(dāng)n>i>j>=0)
例如 1 2 3 4，最小的是1 2 3 4，下一個(gè)是1 2 4 3.。。。最大是4 3 2 1了。
怎么得出當(dāng)前排列的下一個(gè)排列呢？
定義n為數(shù)組P【0,n-1】的長度
下面要考慮的問題，是如何從一個(gè)已知的排列P = p
1p
2…p
n，找到它的下一個(gè)排列
Q = q
1q
2…q
n。我們要讓排列從小到大生成，簡單說，要讓排列的趨勢從P[0..n-1](P[i] > P[j]當(dāng)n>i>j>=0)到P*[0..n-1](P*[i] < P*[j]當(dāng)n>i>j>=0)。
我們可以結(jié)合十進(jìn)制的大小比較來理解。以下以1 3 4 2為例子來說
1.首先從低位找起，找出比高位大的第一個(gè)數(shù)的位置，定義i為這個(gè)位置。(想一下就知道了)若找不到這樣的P[i]，說明我們已經(jīng)找到最后一個(gè)全排列，可以返回了。
1 3 4 2 --> 4比3 大，這個(gè)位置是第2位(1為第0位，3 為第1位)，這時(shí) i = 2
2.再在區(qū)間[i,n-1]中查找比P[i-1]大的最小的數(shù)。
這個(gè)也很容易理解，從例子中看出，這個(gè)最小的數(shù)是4
然后交換兩者，那么現(xiàn)在的數(shù)組是1 4 3 2
3.現(xiàn)在還不是最小的數(shù)，因?yàn)閺牡谝徊降牟檎遥覀冇蠵[i]>P[i+1]> … >P[n-1]，否則查找在i～n就會停下來了。這樣的一個(gè)排列顯然不是最小的。實(shí)際上，原來的P[i...n-1]，已經(jīng)是這一部分最大的一個(gè)排列了。但我們現(xiàn)在換了最高位P[i-1]，因此要讓后面的數(shù)字變的最小。方法很簡單，根據(jù)上面的推理，我們只須將P[i...n-1]的數(shù)列倒置即可（最大的排列倒置就變成了最小的排列）。
回到例子，1 4 3 2 --> 14 2 3得到答案
看完了分析，現(xiàn)在做一題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]的最小數(shù)
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.因?yàn)閺牡谝徊降谩緄,n-1】是遞減的，故第2步中反轉(zhuǎn)p[k],p[i-1]后要把這個(gè)區(qū)間反轉(zhuǎn)
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 閱讀(489)
評論(1) 編輯 收藏 引用