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

Question

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

问题出自codewars Alphabetic Anagrams

我想的笨办法是

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

代码实现

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;
}

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

根据您提供的问题描述，您想要实现一个函数，用于确定给定单词在按字典序排列的所有排列中的位置。您已经尝试了一种方法，但由于性能问题而超时。另外，您提到了一种解决方案，但不太理解其工作原理。
解决这个问题的关键在于理解排列的性质以及如何计算给定排列在所有排列中的位置。这里有一种更高效的方法，可以在不枚举所有排列的情况下计算出位置。
首先，我们来分析一下排列的性质。考虑一个由不同字符组成的单词，例如"hello"。如果将单词中的字符按字典序排列，那么我们可以确定在当前字符固定的情况下，以该字符开头的排列总共有多少个。这个数量可以通过计算当前字符之后有多少个字符比它小来确定。例如，在"hello"中，以"h"开头的排列有多少个？只需要统计在"h"后面有多少个字符比"h"小即可。
接下来，我们可以使用这个思路来计算给定排列的位置。具体步骤如下：

1. 首先，统计给定单词中每个字符的出现次数，并将字符按字典序排序。
2. 遍历给定单词中的每个字符，计算以当前字符开头的排列的数量，并累加到最终结果中。
3. 每次累加时，需要考虑到当前字符已经被使用过的情况，因此需要将该字符的出现次数减1。
   下面是按照上述步骤实现的代码：
   javascriptCopy code

   function listPosition(word) {
   var indexer = {}; // 存储字符在排序后的单词中的索引
   var counts = []; // 存储每个字符的出现次数
   var lettersCount = 0; // 不同字符的数量
   // 统计每个字符的出现次数，并给字符建立索引
   word.split("").sort().forEach(function(x){
   if (indexer[x] === undefined) {
   indexer[x] = lettersCount;
   counts[lettersCount] = 0;
   lettersCount++;
   }
   counts[indexer[x]]++;
   });
   var term = 1; // 用于计算当前字符开头的排列数量的中间项
   var sum = 0; // 最终结果
   // 遍历单词中的每个字符，计算排列的位置
   word.split("").forEach(function(x, i){
   // 计算当前字符之前有多少个字符比它小
   for (var j = 0; j < indexer[x]; j++) {
   // 累加以当前字符开头的排列数量
   if (counts[j] !== 0) {
   sum += term * counts[j] / (i + 1);
   }
   }
   // 更新中间项
   term *= (i + 1) / counts[indexer[x]];
   // 当前字符出现次数减1
   counts[indexer[x]]--;
   });
   return Math.floor(sum) + 1; // 返回位置（从1开始）
   }
   // 示例用法
   var position = listPosition("hello");
   console.log(position); // 输出：24
   

   这个函数通过遍历给定单词中的每个字符，计算了排列的位置，而无需枚举所有排列。这种方法在性能上比较高效，可以快速给出结果。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订