DEV Community

loading...

回溯法 ( Backtracking ) Part 1 - 置換 ( Permutation )

tingwei628 profile image Tingwei ・2 min read

Backtracking 系列文第一篇 !

meme

從 "置換" 談起

什麼是 置換 ( 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)

pic
Editor guide
Collapse
bugb profile image
bugb

I need to use google translate, thank you a lot for sharing with us!

Collapse
tingwei628 profile image
Tingwei Author

Thanks for reading :)
I will try to write the next blog in English !