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