Backtracking 系列文第一篇 !
從 "置換" 談起
什麼是 置換 ( Permutation )?
比如, 三個數字 1, 2, 3 能有幾種排列順序 ? 答案是 6 種 (3! = 唸作 "3的階乘" )
如下 :
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
很簡單吧 XD?
回溯法置換
這邊有兩個題目，邊解釋程式，邊帶觀念!
題目 1 : 陣列 [1, 2, 3]，求置換方式有幾種 ?
註 : 陣列內的數字都是獨一無二的
一開始會想，先取 1 ，然後再找下一個 2 ...到後來 3...
於是，就用到 "回溯法"
回溯法 : 在各種可能方法，並且逐一各個嘗試，成功就走到下一步，一旦失敗就返回上一步
├── [1]
│ ├──────[2]
│ │ │
│ │ └──────[3]
│ │
│ └──────[3]
│ │
│ │
│ └──────[2]
├── [2]
│ ├──────[3]
│ │ │
│ │ └──────[1]
│ │
│ └──────[1]
│ │
│ │
│ └──────[3]
└── [3]
├──────[1]
│ │
│ └──────[2]
│
└──────[2]
│
│
└──────[1]
- 解釋 :
Step 1 : 第一個位置 先選 1, 第二個位置 選 2, 第三個位置 剩下就 3 => ( 1, 2, 3 )
Step 2 : 回到上一步，此時 變成 ( 1, 2 )，第二個位置 選 3，第三個位置 剩下就 2 => ( 1, 3, 2 )
Step 3 : 由於 第二個位置 的 2, 3 都已經置換過了，因此 再回到上一步 !
此時 變成 (1)，第一個位置 改選 2，以此上述Step 1 ~Step 3 規則 置換下去 !
從上面的規則，注意到何時返回上一步 (也就是位置上都有數字的時候 !)
- 程式碼 :
/*
從陣列中移除某數字
remove(1, [1,2,3]) // 返回 [2,3]
*/
function remove(num, arr) {
let index = arr.indexOf(num);
return arr.slice(0, index).concat(arr.slice(index+1));
}
/*
fixed_arr : 已填好位置的陣列
arr : 尚未填入位置的陣列
*/
function permutation(fixed_arr, arr) {
// 全部的數字都填上位置了!
// 返回上一步
if(arr.length === 0) {
// 顯示排列結果
console.log(fixed_arr);
};
// 選擇要填數字
for (let i = 0; i < arr.length; i++) {
// 已選擇好填數字
let fixed_element = arr[i];
// 從"尚未填入位置的陣列" 移除 該已選擇數字
let rest_arr = remove(fixed_element, arr);
// 已選擇數字塞好位置
let new_fixed_arr = fixed_arr.concat(fixed_element);
// 繼續下一步
permutation(new_fixed_arr, rest_arr);
}
}
// 進入點
permutation([], [1,2,3]);
題目 2 : 陣列 [1, 1, 2, 3]，求置換方式有幾種 ?
註 : 陣列內有重複的數字
關鍵 : 在既定位置不允許有重複的數字填入 !
解釋 : [1, 1 ,2, 3]，由於有兩個 1 ，當
第一個 1 佔了第一個位置，就 不允許第二個 1 佔了第一個位置(不然就重複排列 !)
因此，當走每一位置，必須要紀錄該位置的元素 !
- 程式碼 :
function remove(num, arr) {
let index = arr.indexOf(num);
return arr.slice(0, index).concat(arr.slice(index+1));
}
function clone_map(map) {
return new Map(map);
}
function permutation(map, fixed_arr, arr) {
if(arr.length === 0) {
console.log(fixed_arr);
};
//該 index 位置 等於 已填好位置的陣列的長度
//因為要填入新的位置
let index = fixed_arr.length;
for (let i = 0; i < arr.length; i++) {
let fixed_element = arr[i];
// 該位置 index 的數字 如果相等於 已選擇的數字，就不用做
// 因為之前有相同的數字佔領過該 index
if(map.get(index) === fixed_element) continue;
// 如果沒有，及設定該 index 為數字
map.set(index, fixed_element);
let rest_arr = remove(fixed_element, arr);
let rest_map = clone_map(map);
let new_fixed_arr = fixed_arr.concat(fixed_element);
permutation(rest_map, new_fixed_arr, rest_arr);
}
// 返回上一步，就刪除此位置的數字 (回復成上一步的 Map)
map.delete(index);
}
let duplicate_arr = [1,1,3,2,3];
// Map 紀錄位置的元素
// 例如 位置 0 的元素是 1
permutation(new Map(), [], duplicate_arr.sort());
看到這，為什麼一開始要 sort() ?
因為，方便 Map 過濾， 一旦排序好，就不擔心 map 之前的紀錄過的數字，後面又重複出現 !
請看這段程式碼 :
if(map.get(index) === fixed_element) continue;
map.set(index, fixed_element);
未排序 : [1, 2, 3, 1]，當選擇 3，後面的 1，由於和前面的 3不同，被當作是 非重複 的數字
已排序 : [1, 1, 2, 3]，當選擇 1，後面的 1，由於前面的 1，就可以排除掉重複的數字
下一篇，將用 回溯法 ( Backtracking ) 解數獨 ( Sudoku ) 和 寫一個數獨產生器 ( Sudoku Generator )
Discussion (2)
I need to use google translate, thank you a lot for sharing with us!
Thanks for reading :)
I will try to write the next blog in English !