如何快速求一个排列在所有排列中的位置(按字典序排列)?

Question

如何快速求一个排列在所有排列中的位置(按字典序排列)?

问题出自codewars Alphabetic Anagrams

我想的笨办法是

1. 先排序得到最小的排列
2. 和目标排列进行比较，如果相同，结束；否则调用nextPermutation计算出下一个排列
3. 重复步骤2,3

代码实现

function listPosition(word) {
  //Return the anagram list position of the word
  let wd = word.split('').sort();
  
  /*
    wd: Array, represent the current permuation.
    return: Array, represent the next permutation.
     
    https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
  */
  function nextPermutation(a) {
    let n = a.length;
    // 1. find max k, a[k] < a[k+1]
    let k = -1;
    for(let i = 0; i < n - 1; ++i) {
      if(a[i] < a[i+1]) k = i;
    }
    /*
      if k is not exist, state the current permutaion is the max one, don't have next permuation.
    */
    if(k === -1) return -1;
    // 2. find max l, l > k, a[k] < a[l]
    let l = -1;
    for(let i = k + 1; i < n; ++i) {
         if(a[i] > a[k]) l = i;
    }
    // 3. swap a[k] a[l]
    let t = a[k];
    a[k] = a[l];
    a[l] = t;
    // 4. reverse a[k+1...]
    for(let i = k + 1, j = n-1; i < j; ++i, --j) {
      let t = a[i];
      a[i] = a[j];
      a[j] = t;
    }
    return a;
  }
  let i;
  for(i = 1; wd !== -1 && wd.join('') !== word; ++i) {
    wd = nextPermutation(wd);
  }
  return i;
}

但是超时了。

我看解答区的一个答案是这样写的，但是没看懂什么意思。

function listPosition(word) {
    var indexer = {}; // D:3 B:1 A:0 C:2
    var counts = []; // 2 1 1 1

    var lettersCount = 0;
    word.split("").sort().forEach(function(x){
        if ( indexer[x] == undefined ) {
            indexer[x] = lettersCount;
            counts[lettersCount] = 0;
            lettersCount ++;
        }
    });

    var term = 1;
    var sum = term;
    word.split("").reverse().forEach(function(x, i){
        var step = i + 1, idx = indexer[x];
        counts[idx] ++;
        term /= counts[idx];
        for (var j = 0; j < idx; ++j) 
            if (counts[j] != 0) 
                sum += term * counts[j];
        term *= step;
    });
    return sum;
}