DIV CSS 佈局教程網

用 JS 實作陣列的全排列輸出演算法
編輯:JavaScript綜合知識     

全排列是從 n 個不同元素中,任取 m(m ≤ n)個元素按一定順序排成的所有可能;當 m = n 時,就稱為「全排列」。它在許多問題(如旅行推銷員、拼字驗證等)中都是重要的基礎。本文用 JavaScript 以遞迴實作一個陣列的全排列輸出。

核心思路是「逐一挑選」:每次從尚未使用的元素中挑一個放到目前位置,剩下的元素再遞迴處理,直到所有位置都填滿,就得到一組排列;回溯時再把剛才挑的元素放回去,嘗試下一種可能。

function permute(input) {
  var permArr = [];   // 存放所有排列結果
  var usedChars = []; // 目前這條路徑已使用的元素

  function main(input){
    var i, ch;
    for (i = 0; i < input.length; i++) {
      ch = input.splice(i, 1)[0]; // 取出並移除第 i 個元素
      usedChars.push(ch);         // 放入目前排列
      if (input.length == 0) {
        permArr.push(usedChars.slice()); // 排列完成,存一份副本
      }
      main(input);                // 遞迴處理剩下的元素
      input.splice(i, 0, ch);     // 回溯:把元素放回原位
      usedChars.pop();            // 回溯:從目前排列移除
    }
    return permArr;
  }
  return main(input);
}

console.log(permute([5, 3, 7, 1]));

這段程式在舊有寫法上做了一些改進,讓邏輯更清楚:splice(i, 1) 用來「挑出」元素,遞迴返回後再用 splice(i, 0, ch) 把它「放回」原位,完成回溯。對 [5, 3, 7, 1] 執行後,permArr 就會包含全部 24 種排列。理解這個「選擇—遞迴—回溯」的框架,之後要改寫成求部分排列或加上去重條件,都能輕鬆套用。

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