DIV CSS 佈局教程網

JavaScript 實現數組全排列(permutation)
編輯:關於JavaScript     

謎題

給定一個數組,輸出其中所有元素的全排列。

策略

採用「減而治之」配合遞歸:先固定某一個元素作為開頭,再對剩下的元素求全排列,最後把開頭元素拼到每個子排列的前面。問題規模每次縮小一,直到只剩一個元素時遞歸觸底。

JavaScript 實現

/**
 * 求數組的全排列
 */
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!,結果正確。需要提醒的是,全排列的數量隨元素個數呈階乘增長,元素一多就會迅速吃滿記憶體——上面這個版本會把全部結果一次性物化到數組中,實際項目中若只需要流式處理,改成回調或生成器的形式會更省資源。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved