給定一個數組,輸出其中所有元素的全排列。
採用「減而治之」配合遞歸:先固定某一個元素作為開頭,再對剩下的元素求全排列,最後把開頭元素拼到每個子排列的前面。問題規模每次縮小一,直到只剩一個元素時遞歸觸底。
/**
* 求數組的全排列
*/
function getPermutation(arr) {
if (arr.length == 1) {
return [arr];
}
var permutation = [];
for (var i=0; i<arr.length; i++) {
var firstEle = arr[i];
var arrClone = arr.slice(0);
arrClone.splice(i, 1);
var childPermutation = getPermutation(arrClone);
for (var j=0; j<childPermutation.length; j++) {
childPermutation[j].unshift(firstEle);
}
permutation = permutation.concat(childPermutation);
}
return permutation;
}
var permutation = getPermutation(['a','b','c']);
console.dir(permutation);
這裡有兩個細節值得留意:用 slice(0) 複製數組再 splice,是為了避免修改到外層正在遍歷的原數組;用 unshift 把首元素插入子排列,則保證了最終結果的順序符合直覺。
[ [ 'a', 'b', 'c' ], [ 'a', 'c', 'b' ], [ 'b', 'a', 'c' ], [ 'b', 'c', 'a' ], [ 'c', 'a', 'b' ], [ 'c', 'b', 'a' ] ]
三個元素得到 6 種排列,正好是 3!,結果正確。需要提醒的是,全排列的數量隨元素個數呈階乘增長,元素一多就會迅速吃滿記憶體——上面這個版本會把全部結果一次性物化到數組中,實際項目中若只需要流式處理,改成回調或生成器的形式會更省資源。