跳到主要內容

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

留言

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
請教一下,您上述的 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寫道…
謝謝鳥毅大大教學 而且淺顯易懂 新手都能明確看懂 學校目前還剛學到陣列而已~哈哈

這個網誌中的熱門文章

自然人憑證讀卡機驅動程式

鳥毅用的是第一代的自然人憑證讀卡機,EZ100PU(後來有同事買EZmini可以讀SIM卡似乎更好),每年報稅時用一次。 本來只是要申請些政府業務,一時之間找不到光碟,沒想到在 驅動程式下載 居然看到Linux和Mac的驅動程式,剩下的就是政府單位的網頁和程式應該改版了吧!!!

用ZedGraph畫統計圖

Update: 沒想到這篇居然變成Google搜尋ZedGraph第一篇中文網頁,不過還是誠心建議用Windows上的C#先看一下 免費的圖表元件:Microsoft Chart Controls ,除非你非得用.Net 2.0(Windows 2000)或是用 Mono 。 BTW,我並不想成為微軟MVP,所以本Blog並不是有問必答的喲^_^ 才剛貼完上一篇,馬上就有位朋友丟過來一個LGPL Open Source元件的網址: ZedGraph 。 參考: A flexible charting library for .NET