DIV CSS 佈局教程網

用回溯法實作陣列全排列輸出
編輯:關於JavaScript     

從 n 個相異元素中任取 m(m ≤ n)個,按一定順序排好,稱為一個排列;當 m 等於 n 時,所有排列的集合就叫全排列。本文用回溯法把 4 個元素的 24 種排列全部印出來。

function permute(input) {
  var permArr = [], usedChars = [];

  function main(input) {
    var i, ch;
    for (i = 0; i < input.length; i++) {
      ch = input.splice(i, 1)[0];   // 取出
      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) 放回原位、pop() 移出已用序列,讓狀態回到進入這一層之前的樣子。

終止條件是「剩餘集合為空」,此時 usedChars 就是一種完整排列,用 slice() 複製一份存起來——不複製的話,後續回溯會把同一個參照的內容改掉。

時間複雜度是 O(n × n!),n 稍大就會爆炸,所以全排列通常只用在小規模情境,例如拼字遊戲的字元重組或測試資料產生。

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