講解遞迴真的是一門學問阿...希望各位會看懂排列組合的程式碼邏輯: )
用Javascript征服演算法 (1-排列組合-Javascript實作)

各位如果還沒看過上一篇用Javascript征服演算法 (1-排列組合)，請記得在服用本篇之前先去看唷: )(不然應該會看不懂我在寫啥QQ)

一個題目通常都需要經過上篇的推理及最後得出的解法才能夠確實施行在程式碼中，因此如果總是習慣直接寫code來try解法的人，可以試試看下次先推理並筆記下自己的解法，然後再透過程式去實現它，會發現效率很高喔~

話不多說，咱們就來實現上篇的解法吧: ) (本篇程式碼是參考參考資料出處的程式碼作講解)

根據上一篇的解法，我們可以先分析需要那些function，程式盡量模組化會比較簡潔，因此依據上篇解法，應該可以大略分析出，需要幾個功能，分別是"固定集合第一個數字" , "處理剩下集合遞迴產生的新組合" 而透過觀察解法的過程，可以發現以下現象

由圖可知, 紅色框框所表示的都是去做"固定第一個數字"的動作，在此會發現，而在"固定第一個數字"的過程中會去產生新的組合，如綠色框框所示，而"處理剩下集合遞迴產生的新組合"，可看橘色線所示，在[1,2,3,4]的1被固定後，就剩下[2,3,4]的集合了

以上分析有點感覺之後，可以開始來看藍色線所示的尋找新組合的過程，首先是假定我們所要找的集合是[1,2,3,4]的所有排列組合，透過藍色線的指引，首先我們固定了1,然後產生了[2,3,4]的集合，這裡我們開始可以做重複的事情，那就是對[2,3,4]也是做固定2,透過橘色線也可以看見固定2後會產生剩下的集合[3,4],同樣我們也固定了3,透過橘色線看到集合剩下[4],若在固定4,就會發現集合為空了

透過上述一連串的重複動作，從藍色線的方式，可以看見最後找到了[1,2,3,4]及[1,2,4,3]這兩個集合，其他組合也可以透過上述流程找到

一旦在分析時有了重複動作，就代表可以透過迴圈或是遞迴的方式來撰寫出程式碼了，因此我們來試試看撰寫"固定第一個數字"並"切割剩下的集合"的程式碼

var list = [1,2,3,4];
    var pl = [];
    pl.push(list[0]);//將第一個數字存入pl
	list.slice(1, list.length);//切割剩下的集合=>[2,3,4]

以上並未完成"固定第一個數字"，因為以上程式碼只固定了集合第一個元素list[0], 因此接下來我們需要去撰寫該如何旋轉集合，讓他能夠做到圖中紅色框框的部分，固定集合其他元素成為第一個數字

function rotatedTo(i) {//要固定第i個數字
        var rotated = [];
        rotated.push(list[i]);//先將第i個數字存入陣列當成第一個數字
        return rotated.concat(list.slice(0, i))
                      .concat(list.slice(i + 1, list.length));//將第i個數字之前的集合元素先加到後面,之後再將第i個數字之後的集合元素加到陣列之後,以[1,2,3,4]為例,假設要將第二個數字2提前放在第一個數字,在rotated.push(list[i]);終究會將2放到陣列裡,而後會將2之前的數字1放到2之後,再將2之後的3,4放到之後,因此就會產生[2,1,3,4]
    }

	var all = [];//儲存rotatedto所return後的所有陣列
    for(var i = 0; i < list.length; i++) {
        all.push(rotatedTo(i));
    }
    return all;//ex: all= [[1,2,3,4],[2,1,3,4]....];

#以上完成後，我們的程式也大致底定, 其實透過圖就可知道,透過不斷對剩下集合做以上事情(固定第一個數字)，就可以獲得所有的排列組合

###在此會有一個疑問是，程式何時知道集合已經找完?從圖中的藍色線可知道,切割集合到最後會得到一個空集合,因此只要判斷到空集合就可知道不需要再繼續切割集合了

if(list.length == 0) {
        pls.push([]);
    } 

	return pls;

結合以上程式碼之後，我們可以得出下面的完整程式碼

function allRotated(list) {
    function rotatedTo(i) {
        var rotated = [];
        rotated.push(list[i]);
        return rotated.concat(list.slice(0, i))
                      .concat(list.slice(i + 1, list.length));
    }

    var all = [];
    for(var i = 0; i < list.length; i++) {
        all.push(rotatedTo(i));
    }
    return all;
	}

	function perm(list) {
    var pls = [];
    if(list.length == 0) {
        pls.push([]);
    } else {
        allRotated(list).forEach(function(lt) {
            perm(lt.slice(1, lt.length)).forEach(function(tailPl) {
                var pl = [];
                pl.push(lt[0]);
                pls.push(pl.concat(tailPl));
            });
        });
    }
    return pls;
	}

	perm([1, 2, 3, 4]).forEach(function(lt) {
   		console.log(lt);
	});

以上比較需要特別講解的就是allRotated會去call pem這件事情，第一次的allRoatated會去產生[1,2,3,4],[2,1,3,4],[3,1,2,4],[4,1,2,3],而之後會去做將切割後的集合ex:[2,3,4]在去做同樣的重複動作事情,因此就會在call一次pem

以上說明可能需要自己再去理解，如果很難懂，可以看以下我畫得圖後應該會比較好理解

今天就講解到這邊，如果想直接看成果，可以到以下連結，打開webconsole就可以看到[1,2,3,4]的所有排列組合囉~

http://jsfiddle.net/stanney/LDF3P/1/

今日學習到的javascript新function

.slice //做為切割陣列用
.push //可將元素丟入陣列中
.concat //連接元素非常好用的function

可以透過以下連結去看javascript的function詳細解釋: )

http://msdn.microsoft.com/zh-tw/library/ie/tkcsy6fe(v=vs.94).aspx