DIV CSS 佈局教程網

JavaScript 演算法:求不重複 N 位數的排列序號
編輯:關於JavaScript     

本題要求從 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));

這個演算法的優點,是不需要真正建立全部排列,而是利用數學計數直接推導序號。它更省時間,也更省記憶體。

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