DIV CSS 佈局教程網

JavaScript 解三階幻方(九宮格):遞歸與非遞歸的全排列
編輯:關於JavaScript     

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

策略:窮舉搜尋——列出所有整數排列方案,再逐一過濾。亮點在於遞歸函式 getPermutation 的設計;文末另外提供幾種非遞歸的全排列演算法。

// 遞歸版全排列:直觀但資源消耗大
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;
}

// 驗證是否為幻方
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];
}

var permutation = getPermutation([1,2,3,4,5,6,7,8,9]);
var candidate;
for (var i = 0; i < permutation.length; i++) {
    candidate = permutation[i];
    if (validateCandidate(candidate)) { break; } else { candidate = null; }
}
console.log(candidate ? candidate : 'No valid result found');

非遞歸解法一:求模法

/* 演算法示例(以 4 個元素 ["a","b","c","d"] 為例,共循環 4! = 24 次):
 * 假設 index = 13,因為共 4 個元素,故迭代 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++) {       // 每個 index 對應一個排列
        var t = index;
        for (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; }
    }
}
perm([1,2,3,4,5,6,7,8,9]);

非遞歸解法二:回溯(位置編碼)

// 以「位置編碼」陣列做回溯,index[n] 表示第 n 個位置放了哪個元素
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);   // 初始化為 1,2,3,...,-1

    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; }
    }
}
perm([1,2,3,4,5,6,7,8,9]);

非遞歸解法三:下一個排列(字典序)

/* 全排列(非遞歸求順序)演算法
 * 1、建立位置陣列,對位置做排列,成功後轉為元素的排列;
 * 2、設 P 是 1~n 的一個全排列 p1,p2...pn:
 *   (1) 從尾部開始,找出第一個比右邊小的位置索引 j,即 j = max{i | pi < pi+1}
 *   (2) 在 pj 右邊找出所有比 pj 大的位置中最小的索引 k
 *   (3) 交換 pj 與 pk
 *   (4) 將 pj+1...pn 翻轉,得到下一個排列 p'
 *
 * 例:24310 的下一個排列
 *   (1) 由右至左找出第一個比右邊小的數字 → 2
 *   (2) 在 2 之後找出比 2 大且最小者 → 3
 *   (3) 交換 2 與 3 → 34210
 *   (4) 翻轉 3 之後的所有數字(4210 → 0124)→ 30124
 */
function swap(arr, i, j) {
    var t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}

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

    // 找出比 j 位置的值大的最小者 k(由尾端往前找)
    for (var 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 個排列,適合需要隨機取樣的場合;回溯法概念最貼近遞歸;字典序法則是實務上最常用的一種,因為它能以「 continually 取下一個」的方式逐個產出,記憶體用量固定。

不過就這個題目而言,窮舉 362,880 個排列其實是殺雞用牛刀。三階幻方的中心格必定是 5(因為所有幻和為 15,而 5 被四條線共用),由此出發做剪枝,可以瞬間把搜尋空間縮到幾千個候選;幻方的本質解法更可直接用 Siamese 法(奇階幻方演算法)一步填完。這也是algorthm 設計上常見的取捨:暴力法好寫好驗證,但一旦理解問題的結構對稱性,往往能少做幾個數量級的工作。

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