星期三, 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:感謝破百的老兵指正。

9 則留言:

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吧 ^_^

柳維碩 提到...

你好 剛好學校作業有這題 請問一下 如果不知道輸入有幾個 陣列要怎麼辦 有可能題目出1-7 或是1-5 1-10 都有可能 就不能像上面那樣宣告了

Tseng Teng-Yi 提到...

柳同學:
你要加強基本功才是呀!這叫做Dynamic Array 。若是C用malloc,C++用new。
隨便寫寫,請在作業後面註明:感謝鳥毅教導C++,哈哈。

#include
#include
using namespace std;
int main()
{
int size;

cout << "請輸入陣列大小 1 ~ 10: ";
cin >> size;
int *a = new int[size];
for(int i=0; i<size; i++)
{
a[i] = i+1;
}
do
{
for(int i=0; i< size; i++)
{
cout << a[i] << " ";
}
cout << endl;
}while (next_permutation(a, a+size));
delete [] a;
return 0;
}

柳維碩 提到...

謝謝鳥毅大大教學 而且淺顯易懂 新手都能明確看懂 學校目前還剛學到陣列而已~哈哈