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

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

Answer 1

这段代码是用JavaScript编写的，用于快速求一个排列在所有排列中的位置（按字典序排列）。

代码的思路如下：

1. 创建一个indexer对象和一个counts数组。indexer对象用于存储每个字母在排序后的字符串中的位置，counts数组用于存储每个字母的出现次数。
2. 遍历输入的字符串，对每个字母进行排序，并更新indexer和counts数组。
3. 初始化变量term为1，sum为term。
4. 遍历排序后的字符串的逆序，更新counts数组和term、sum的值。
5. 返回sum作为结果。

具体实现中，使用了动态规划的思想，通过计算每个字母在排列中的位置和出现次数，逐步推导出最终的位置。其中，term表示当前位置相对于最前面非零出现次数的位置的倍数，sum表示从最前面非零出现次数到当前位置的所有排列的个数之和。

需要注意的是，由于使用了动态规划的思想，这段代码的时间复杂度为O(n)，其中n是输入字符串的长度。