全排列是從 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 種排列。理解這個「選擇—遞迴—回溯」的框架,之後要改寫成求部分排列或加上去重條件,都能輕鬆套用。