用遞迴產生所有排列

本來要解的題目其實是算法競賽入門經典習題 2-6：

用 1,2,3,...,9 組成 3 個三位數 abc, def, ghi, 每個數字恰好使用一次，要求 abc:def:ghi = 1:2:3。按照 "abc def ghi" 的格式輸出所有解，每行一個解。提示：不必太動腦筋。(這裡有一份題解，效率比列出所有的排列高)

因為曾經在冼鏡光老師的書上看過「產生所有排列」這個題目，所以對我來說不必太動腦筋的作法就是引用書上的成果，翻開目錄發現自己以前做過「問題 3-4： 產生所有排列 - 旋轉法」這一題，事隔多年，是否有可能看題目說明就解出答案呢？

結果發現自己還是差那麼一步，只好作弊偷瞄答案，不過在自尊性作祟下只看了 10 秒，看到有兩個迴圈自己再摸索一下很快就解出來了。解完才赫然發現，整個解題的方法就藏在題目的說明中，才悟出一個道理：

「解題的成功與否，往往與你能把題目看得多深多透有關」

但是這樣還是沒什麼成就感，接著看到習題1.要求把程式改成用遞迴，沒想到讓我挑戰成功了，下面就是解答：

#include <stdio.h>
#include <vector>

void dumpv(std::vector<int>& v);
void init(std::vector<int>& v);
void rotate(std::vector<int> &ary, int n);
void perm(std::vector<int>& v, int& pos);

int size;
int pos;
std::vector<int> v;

int main(int argc, char *argv[])
{
    size = 4;
    v.resize(size);
    init(v);
    
    pos = size - 1;
    dumpv(v);    
    rotate(v, pos);
    perm(v, pos);
    
    return 0;
}

void dumpv(std::vector<int>& v)
{
    for(size_t i = 0; i < v.size(); ++i)
        printf("%d", v.at(i));
    
    printf("\n");
}

void rotate(std::vector<int> &ary, int n)
{
    const int tmp = ary[n];
    for(int i = n; i > 0; --i)
        ary[i] = ary[i-1];

    ary[0] = tmp;
}

void init(std::vector<int>& v)
{
    for(int i = 0; i < (int)v.size(); ++i)
        v[i] = i+1;    
}


void perm(std::vector<int>& v, int& pos)
{
    if(pos <= 0)
        return;
    
    if(v[pos] == pos + 1)
    {
        --pos;
        rotate(v, pos);
        perm(v, pos);
    }
    else
    {
        pos = size - 1;
        dumpv(v);
        rotate(v, pos);
        perm(v, pos);
    }
}

數學中有個「Fubini 原理」，大意是說「用兩個方法算同一個量，結果會一樣。」在程式設計的領域上也許可以推廣成「用迴圈能寫出的程式，用遞迴也可以寫出來」，這樣做有什麼好處？有人說學了 Functional Programming 會讓你成為一個更好的程式設計者，其中的道理就是強迫你從不同的路徑解決同樣的問題，加深對問題本質的理解。最後讓小弟引用一下計算機科學大師 Robert W. Floyd 在 1978 年領取 Turing Award 時講的一段講稿(取自 More Programming Pearls)： 

在我自己設計困難算法的經驗中，我發現了一個擴展自己能力的方法。一個具有挑戰性的問題解決後，我從頭再做一遍，回顧之前的方法中的閃光點。我重複這樣做，直到解決方法如我所希望的那樣明確跟直接。然後我考慮類似問題的通用準則，這將促使我在起初的時候最有效的解決問題。通常，這樣的法則具有永久的價值。