DIV CSS 佈局教程網

用 JavaScript 解三階幻方:四種全排列策略實作與比較
編輯:JavaScript綜合知識     

題目:將 1~9 這九個不重複的整數填入 3×3 的方格,使得每一列、每一行以及兩條對角線上的數字總和都相等。

策略:窮舉搜尋。先列出所有可能的填法(也就是 1~9 的全排列,共 9! = 362880 種),再逐一過濾出符合條件的答案。

本文的看點在於四種全排列實作的對比:遞迴、求模法、回溯法,以及字典序下一個排列法。

驗證函式

不管是哪一種排列演算法,最後都需要同一組驗證邏輯:

function validateCandidate(candidate) {
  var sum = candidate[0] + candidate[1] + candidate[2];

  for (var i = 0; i < 3; i++) {
    if (!(sumOfLine(candidate, i) == sum && sumOfColumn(candidate, i) == sum)) {
      return false;
    }
  }

  return sumOfDiagonal(candidate, true) == sum
      && sumOfDiagonal(candidate, false) == sum;
}

function sumOfLine(candidate, line) {
  return candidate[line * 3] + candidate[line * 3 + 1] + candidate[line * 3 + 2];
}

function sumOfColumn(candidate, col) {
  return candidate[col] + candidate[col + 3] + candidate[col + 6];
}

function sumOfDiagonal(candidate, isForwardSlash) {
  return isForwardSlash
       ? candidate[2] + candidate[4] + candidate[6]
       : candidate[0] + candidate[4] + candidate[8];
}

解法一:遞迴全排列

function getPermutation(arr) {
  if (arr.length == 1) return [arr];

  var permutation = [];
  for (var i = 0; i < arr.length; i++) {
    var firstEle = arr[i];          // 取出頭一個元素
    var arrClone = arr.slice(0);    // 複製陣列
    arrClone.splice(i, 1);          // 從複本中移除,縮小問題規模

    var childPermutation = getPermutation(arrClone);  // 遞迴求解子問題
    for (var j = 0; j < childPermutation.length; j++) {
      childPermutation[j].unshift(firstEle);          // 把取出的元素拼回每個子排列前面
    }
    permutation = permutation.concat(childPermutation);
  }
  return permutation;
}

思路優雅,但代價是把 36 萬個排列全部存在記憶體裡,非常耗資源。實務上應該改成「找到一組就停」的寫法。

解法二:求模法(非遞迴)

這個演算法很巧妙:把「第 n 個排列」直接映射成一組餘數。

以 4 個元素 ["a","b","c","d"]、index = 13 為例,共需迭代 4 次:

  • 第 1 次:13 ÷ 1,商 13、餘 0 → 把第 1 個元素插到位置 0,得 ["a"]
  • 第 2 次:13 ÷ 2,商 6、餘 1 → 把第 2 個元素插到位置 1,得 ["a","b"]
  • 第 3 次:6 ÷ 3,商 2、餘 0 → 把第 3 個元素插到位置 0,得 ["c","a","b"]
  • 第 4 次:2 ÷ 4,商 0、餘 2 → 把第 4 個元素插到位置 2,得 ["c","a","d","b"]
function perm(arr) {
  var result = new Array(arr.length);
  var fac = 1;
  for (var i = 2; i <= arr.length; i++) fac *= i;   // 算出總排列數

  for (var index = 0; index < fac; index++) {
    var t = index;
    for (var i = 1; i <= arr.length; i++) {
      var w = t % i;                       // 決定插入位置
      for (var j = i - 1; j > w; j--) {    // 往後挪,騰出空位
        result[j] = result[j - 1];
      }
      result[w] = arr[i - 1];
      t = Math.floor(t / i);
    }
    if (validateCandidate(result)) {
      console.log(result);
      break;
    }
  }
}

解法三:回溯法(非遞迴)

用一個「位置陣列」記錄每個元素被放在第幾個位置,逐一嘗試並偵測衝突:

function seek(index, n) {
  var flag = false, m = n;
  do {
    index[n]++;                          // 嘗試下一個位置
    if (index[n] == index.length) {      // 已無位置可用
      index[n--] = -1;                   // 重置並退回上一個元素
    }
    else if (!(function () {
      for (var i = 0; i < n; i++) {      // 檢查是否與前面元素衝突
        if (index[i] == index[n]) return true;
      }
      return false;
    })()) {
      if (m == n) flag = true;           // 已到最後一個元素,找到完整排列
      else n++;                          // 否則往下一個元素前進
    }
  } while (!flag && n >= 0);
  return flag;
}

function perm(arr) {
  var index = new Array(arr.length);
  for (var i = 0; i < index.length; i++) index[i] = -1;
  for (i = 0; i < index.length - 1; i++) seek(index, i);

  while (seek(index, index.length - 1)) {
    var temp = [];
    for (i = 0; i < index.length; i++) temp.push(arr[index[i]]);
    if (validateCandidate(temp)) {
      console.log(temp);
      break;
    }
  }
}

解法四:字典序下一個排列(最推薦)

這是最經典也最有效率的做法。給定一個排列,求下一個排列的四個步驟:

  1. 從右往左找出第一個「比右邊數字小」的索引 j,即 j = max{i | p[i] < p[i+1]}
  2. 在 j 右側找出所有比 p[j] 大的數中最小的那個,索引 k
  3. 交換 p[j] 與 p[k]
  4. 把 j 右側的所有數字翻轉

例如 24310 的下一個排列:從右往左找到第一個比右邊小的是 2;它後面比 2 大的數中最小的是 3;交換後得 34210;再把 2(現在是 3)後面的 4210 翻轉成 0124,答案是 30124。

function swap(arr, i, j) {
  var t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}

function sort(index) {
  // 從尾端找出第一個「左邊小於右邊」的位置
  var j;
  for (j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--);
  if (j < 0) return false;               // 已是最大排列,全部列完

  // 從尾端找出比 index[j] 大的數中最小的
  var k;
  for (k = index.length - 1; index[k] < index[j]; k--);

  swap(index, j, k);

  // 翻轉 j+1 到尾端
  for (j = j + 1, k = index.length - 1; j < k; j++, k--) {
    swap(index, j, k);
  }
  return true;
}

function perm(arr) {
  var index = new Array(arr.length);
  for (var i = 0; i < index.length; i++) index[i] = i;

  do {
    var temp = [];
    for (i = 0; i < index.length; i++) temp.push(arr[index[i]]);
    if (validateCandidate(temp)) {
      console.log(temp);
      break;
    }
  } while (sort(index));
}

perm([1, 2, 3, 4, 5, 6, 7, 8, 9]);

四種解法的取捨

  • 遞迴程式碼最短,但會一次產生全部排列,記憶體開銷最大。
  • 求模法可以「跳到第 N 個排列」,適合需要隨機取樣的場景,但每組都要重算。
  • 回溯法不佔額外記憶體,邏輯稍複雜,適合需要中途剪枝的問題。
  • 字典序法是實務首選:空間 O(1)(只需一組索引)、時間均勻,且能自然地在找到答案後提早結束。

順帶一提,三階幻方的答案其實只有 8 組(考慮旋轉與鏡射後本質上只有 1 組),中心格必定是 5,四角必為偶數。知道這些數學性質後,其實可以跳過窮舉直接構造——但從演算法學習的角度,把四種全排列都寫一遍仍然很值得。

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