DIV CSS 佈局教程網

JavaScript 演算法:求 N 位不重複數字的字典序排列序號
編輯:JavaScript綜合知識     

這是一道經典的排列序號問題:從 1 到 9 中選取 N 個數字,組成不重複的 N 位數,並按從小到大編號。給定其中任一個數 M,要能算出它對應的序號。

例如 N=3、M=213 時,全部排列為:

[123(1), 132(2), 213(3), 231(4), 312(5), 321(6)]  →  X = 3

思路分析

最直接的想法是先生成從小到大排列的完整陣列,再透過索引取得序號;但當 N 很大、甚至推廣到 16 或 36 進制時,這種暴力法既耗時又浪費空間。因此我們改用「逐位計算」的方式。

以 213 為例:首位是 2,代表所有以 1 開頭的排列(123、132)都排在它前面,共 2 個;接著看第二位 1,後面剩下的數字中沒有比它更小的,貢獻 0;第三位是個位,前面都確定後只剩唯一可能,貢獻 0。合計 2,所以它排在第 3 位。

程式實作

// 計算某一位若放更小的數字,比當前小的排列總數
// a:當前位數值在所有可用數字中的排名(從小到大)
// n:當前位剩餘可排列的數量
function getAll(a, n){
  var sum = 1;
  for (var i = n; i > 1; i--) sum = sum * i; // n 的階乘,即 n 個位置的全排列數
  return sum * (a - 1) / n;                  // 首位比 a 小的可能性總數
}

function find(m){
  m = (m + "").split("");                    // 拆成單字元陣列
  // 建立長度與 m 相同、初值皆為 1 的 a 陣列
  var a = new Array(m.length + 1).join(1).split("");
  // 計算 a:每一位在其後數字中的排名
  for (var i = 0; i < m.length - 1; i++){
    for (var j = i + 1; j < m.length; j++){
      if (+m[i] > +m[j]) a[i]++;
    }
  }
  var sum = 1;
  for (var i = 1; i < m.length; i++){
    sum += getAll(+a[i - 1], m.length - i + 1);
  }
  return m + " 排在全排列的第 " + sum + " 位";
}

console.log(find(213)); // 第 3 位
console.log(find(123)); // 第 1 位
console.log(find(231)); // 第 4 位
console.log(find(312)); // 第 5 位
console.log(find(4321));// 第 24 位

這裡的關鍵是 getAll 函式:它用「剩餘位數的階乘」乘上「該位比目前數字小的比例」,算出這一位能貢獻多少個更小的排列,再逐位累加並加一,就是最終序號。相較於暴力生成,這種做法不必實際展開所有排列,時間與空間都更有效率。

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