從 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 稍大就會爆炸,所以全排列通常只用在小規模情境,例如拼字遊戲的字元重組或測試資料產生。