排列演算法

數學一向不是很好的我，一看到要列出某字串所有的排列(Permutation)，就讓我非常的頭大。記得當初要準備考研究所時就曾經看著資料結構書上的解法想了老半天，似懂非懂，但最近又看到類似的題目，證明了以前是裝懂。

To iterate is human, to recurse divine.

遞迴的程式一定要在頭腦清楚時再來看，否則只是在浪費時間而已。這次，我真的看懂了。

以{a, b, c, d}為例子，要列出所有的排列，我們可以將這個問題拆解成：

• 開頭為a加上{b, c, d}的所有排列
• 開頭為b加上{a, c, d}的所有排列
• 開頭為c加上{a, b, d}的所有排列
• 開頭為d加上{a, b, c}的所有排列

所以，很明顯的是可以用遞迴方式來解。在此用C++來實作

void perm(char *obj, int pos, int n) {
if(pos == n - 1) {
for(int i = 0; i < n; ++i) cout << obj[i] << " ";
cout << endl;
}
else {
for(int i = pos; i < n; ++i) {
// swap()是要自己寫的函式，交換陣列內的值
swap(obj[pos], obj[i]);
perm(obj, pos + 1, n);
swap(obj[pos], obj[i]);
}}}
else內的for迴圈是整個程式的關鍵，可以用上面舉的例子來說明，假設obj陣列已經存了{a, b, c, d}四個值，我們呼叫perm(obj, 0, 4)來印出所有排列。for迴圈的解釋就如同將第一個位置分別用a, b, c, d為開頭，所以用了swap()把每一個值都對調到第一個位置，接著再呼叫perm(obj, 1, 4)來排列剩下的三個字元，依此類推。