2016年6月21日 星期二

用遞迴產生所有排列

本來要解的題目其實是算法競賽入門經典習題 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): 

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

2 則留言:

  1. 分享另一種遞迴解法
    void perm2(std::vector&, int = 1);
    int main(void){
    size = 4;
    v.resize(size);
    init(v);

    perm2(v);

    return 0;
    }
    void perm2(std::vector& v, int m){
    for(int j=0; j<m; j++){
    if(m == size) dumpv(v);
    else perm2(v, m+1);
    rotate(v, m-1);
    }
    }

    回覆刪除