javascript - 在所有可能的排列列表中查找给定字符串的排名

Question

我试图在可能的排列列表中找到给定字符串的排名。我试图想出一个解决方案，试图找到所有可能的排列，为它们分配一个等级，然后显示它。

但是当字符串的长度不断增加时，这会大大降低性能。所以想知道是否有人可以为这个问题想出一个有效的解决方案..

function permute(str) {
    // Sort the string
    var arr = [];
    for (var i = 0; i < str.length; i++) arr.push(str[i]);
    var sortedString = arr.sort().join(''),
        // Length of the string
        length = str.length,
        used = [];
    // Create a boolean array for length of the string
    while (length--) used.push(false);
    // String buffer that holds the current string
    var out = '';
    // Call the function
    doPermute(sortedString, str, out, used, str.length, 0);
}
var count = 0;

function doPermute(inp, givenString, out, used, length, level) {
    // Only if length of the string equal to current level print it
    // That is permutation length is eqaul to string length
    if (level == length) {
        count++;
        //console.log('Perm :: ' + out + ' -- ' + count);
        if (out === givenString) {
            var pp = 'Rank of  :: ' + out + ' -- ' + count;
            $('div').append('<p>' + pp + '</p>');
        }
        return;
    }
    for (var i = 0; i < length; ++i) {
        // If variable used continue
        if (used[i]) continue;
        // Append the current char in loop
        out += inp[i];
        // set variable to true
        used[i] = true;
        // Call the function again
        doPermute(inp, givenString, out, used, length, level + 1);
        // Set it to false as the variable can be reused
        used[i] = false;
        // remove the last character of the buffer
        out = out.slice(0, out.length - 1)
    }
}

permute('dbcarf')

Fiddle

Answer 1

确定:如果输入字符串是 "cab".一个以c开头的字符串能得到的最低排名是多少？

c请注意它之前的字符串。

abc
acb
bac
bca

所以以 c 开头的字符串的最小等级为 5。这只是输入字符串中按字典顺序排在 c 之前的字符数。(按顺序 a、b、c、d、e、f...)所以我们有2.每个以字母开头的单词可以有2个单词。
下一个字母是“a”？
以“ca”开头的单词最低排位是多少？
5
为什么？
“a”是我们用剩余字母填充第二个位置的最佳方式。
第三个元素“b”也是如此。
所以“cab”的等级是 5。

一般。(假设没有重复，虽然这并不难)

var W; //input string
 var C[26];
 var rank = 1;
 for (var i = 0; i < W.length; i++) C[W[i] - 'a']++;
 for (var i = 0; i < W.length; i++) {
     //How many characters which are not used, that come before current character
     var count = 0;
     for (var j = 0; j < 26; j++) {
         if (j == (W[i] - 'a')) break;
         if (C[j] > 0) count++;
     }
     C[W[i] - 'a'] = 0;
     rank += count * fact(W.length - i - 1);
 }