本題要求從 1 到 9 中選取 N 個不重複數字,組成 N 位數,並依大小排序後,找出某個數字的序號。例如 N 為 3,M 為 213,則序號為 3。
若直接建立所有排列再搜尋,雖然可行,但會浪費時間與空間。更好的方式,是逐位計算比當前數字小的可能性。
以 213 為例,首位是 2,比 2 小的可用數字只有 1,因此首位為 1 的排列都排在前面。接著看第二位,13 中 1 已是最小,所以沒有更小的排列。最後一位則不需再計算。
可先寫一個函式,計算某一位在剩餘數字中比當前值小的可能性。
function getAll(a, n) {
var sum = 1;
for (var i = n; i > 1; i = i - 1) {
sum = sum * i;
}
return sum * (a - 1) / n;
}接著,將數字拆成陣列,逐位判斷後面有多少數字比目前數字小。
function find(m) {
m = String(m).split('');
var a = [];
for (var i = 0; m.length > i; i = i + 1) {
a.push(1);
}
for (var j = 0; m.length - 1 > j; j = j + 1) {
for (var k = j + 1; m.length > k; k = k + 1) {
if (Number(m[j]) > Number(m[k])) {
a[j] = a[j] + 1;
}
}
}
var sum = 1;
for (var x = 1; m.length > x; x = x + 1) {
sum = sum + getAll(Number(a[x - 1]), m.length - x + 1);
}
return sum;
}console.log(find(213));
console.log(find(123));
console.log(find(231));
console.log(find(312));這個演算法的優點,是不需要真正建立全部排列,而是利用數學計數直接推導序號。它更省時間,也更省記憶體。