Finding the rank of the Given string in list of all possible permutations

Question

I am trying to find the Rank of the given string in the list of possible permutations. I tried to come up with a solution that tries to find all possible permutations, assign a rank to them and then display it.

But this drastically reduces the performance when the length of the string keeps increasing. So was wondering if someone can think of an efficient solution for this problem..

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

Sure: if input string is "cab". What is the lowest rank that a string starting with c could get?

c Note the strings that come before it.

abc
acb
bac
bca

So a string starting with c has minimum rank 5.This is just number of characters in input string that come lexicographically before c.(in order a,b,c,d,e,f...)So we have 2.Each word starting with a letter can have 2 words.
Next letter is "a"?
What is minimum rank that a word starting with "ca" can get?
5
Why?
"a" is the best way we can fill the second spot with the remaining letters.
And the same goes for third element "b".
So rank of "cab" is 5.

In general.(Assuming no duplicates, though this is not much harder)

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