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 閱讀(481)
評論(1) 編輯 收藏 引用