星期三, 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.

匿名 提到...

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

鳥毅 提到...

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

泰北進修_98資3忠 提到...

請教一下,您上述的 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吧 ^_^

Unknown 提到...

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

鳥毅 提到...

柳同學:
你要加強基本功才是呀!這叫做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;
}

Unknown 提到...

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