星期三, 8月 22, 2007

STL的next_permutation

忘了在哪個站看到,題目是:"把 1、2、3、4、5 的所有排列情形列出",格主說他當時不會用recursive,就用迴圈做出,留言裏有提到STLnext_permutation,今天抽空試了一下多年沒碰的STL
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1,2,3,4,5};
do
{
cout << a[0] << " " << a[1] <<  " " <<  a[2] <<  " " <<  a[3] <<  " " <<  a[4] <<  endl;
}while (next_permutation(a,a+5));
return 0;
}
果然是很優雅的寫法,看來這演算法也可應用到棋盤的窮舉法呀!

注意:若要走遍所有的排序,next_permutation的輸入必須由小到大排序過,prev_permutation是由大到小排序。所以若使用亂序的陣列做列舉,記得要先排序。

Update:感謝破百的老兵指正。

6 則留言:

ijliao 提到...

並沒有規定一定要 sort 過才能跑 {next,pre}_permutation(), 你看 sgi doc 裡面最後的 snail_sort() 就是很好的例子

鳥毅 提到...

廖大,你說的沒錯,不過若要走遍所有的排列而不是排序,必須要先排序。

sgi doc Notes:
[2] Note that the lexicographically smallest permutation is, by definition, sorted in nondecreasing order.

Gogo 提到...

哈囉
請問可以參考你的文章
放在我的報告裡嗎

鳥毅 提到...

沒問題,版權沒有,歡迎抄襲 XD

Chen 提到...

請教一下,您上述的 code可以在哪個平台上compile and run?Linux or Windows...

因為要寫一個52!的perm...還需要改寫..

thanks in adv.

鳥毅 提到...

Chen, 你應該問用什麼編譯器會過,基本上STL與平台無關呀!我在FreeBSD、Windows、Linux和Mac用gcc 4.2都沒問題,Visual Studio 2008的C++ compiler也可以。所以在熟悉的平台用gcc或MSC吧 ^_^