跳到主要內容

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的驅動程式,剩下的就是政府單位的網頁和程式應該改版了吧!!!

在Windows Server設定L2TP over IPSec VPN

簡單地說,macOS Sierra與iOS 10發表後,大家忽然發現Apple不再支援PPTP,所以一定得設定其他的VPN型態。若不要另外裝client,用L2TP是最方便的,SSL VPN雖然好,但若沒有安裝Agent要連線到任一電腦或是非網頁服務還是挺麻煩的。