CODEWITHSUNDEEP
javascriptperformancealgorithmranking
Sushanth --
Sushanth --

Reputation: 55750

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

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

Upvotes: 0

Views: 979

Answers (2)

Aravind
Aravind

Reputation: 3199

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

Upvotes: 2

mcdowella
mcdowella

Reputation: 19621

There is an explanation in https://en.wikipedia.org/wiki/Permutation#Numbering_permutations of how to convert a permutation on n objects to a number in the range 0..n!-1 and it goes on to say that "Converting successive natural numbers to the factorial number system produces those sequences in lexicographic order (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used" So I would try doing this number conversion and see if it produces something related to the rank that you need, by your definition.

Upvotes: 0

Related Questions