Find the index of a given permutation in the sorted list of the permutations of a given string

We're given a string and a permutation of the string.

For example, an input string sandeep and a permutation psdenae.

Find the position of the given permutation in the sorted list of the permutations of the original string.

Solution 1:

The total number of permutation of a given string of length n would be n! (if all characters are different), thus it would not be possible to explore all the combinations.

This question is actually like the mathematics P & C question

Find the rank of the word "stack" when arranged in dictionary order.

Given the input string as NILSU Take a word which we have to find the rank. Take "SUNIL" for example.

Now arrange the letter of "SUNIL" in alphabetical order.

It will be. "I L N S U".

Now take the first letter. Its "I". Now check, is the letter "I" the first letter of "SUNIL"? No. The number of words that can be formed starting with I will be 4!, so we know that there will be 4! words before "SUNIL".

I = 4! = 24

Now go for the second letter. Its "L". Now check once again if this letter we want in first position? No. So the number of words can be formed starting with "L" will be 4!.

L = 4! = 24

Now go for "N". Is this we want? No. Write down the number of words can be formed starting with "N", once again 4!

N = 4! = 24

Now go for "S". Is this what we want? Yes. Now remove the letter from the alphabetically ordered word. It will now be "I L N U"

Write S and check the word once again in the list. Is we want SI? No. So the number of words can be formed starting with SI will be 3!

[S]:I-> 3! = 6

Go for L. is we want SL? No. So it will be 3!.

[S]:L-> 3! = 6

Go for N. is we want SN? No.

[S]:N-> 3! = 6

Go for SU. Is this we want? Yes. Cut the letter U from the list and then it will be "I L N". Now try I. is we want SUI? No. So the number of words can be formed which starts from SUI will be 2!

[SU]:I-> 2! = 2 Now go for L. Do we want "SUL". No. so the number of words starting with SUL will be 2!.

[SU]:L-> 2! = 2

Now go for N. Is we want SUN? Yes, now remove that letter. and this will be "I L". Do we want "SUNI"? Yes. Remove that letter. The only letter left is "L".

Now go for L. Do we want SUNIL? Yes. SUNIL were the first options, so we have 1!. [SUN][I][L] = 1! = 1

Now add the whole numbers we get. The sum will be.

24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95.

So the word SUNIL will be at 95th position if we count the words that can be created using the letters of SUNIL arranged in dictionary order.

Thus through this method you could solve this problem quite easily.

Solution 2:

Building off @Algorithmist 's answer, and his comment to his answer, and using the principle discussed in this post for when there are repeated letters, I made the following algorithm in JavaScript that works for all letter-based words even with repeated letter instances.

function anagramPosition(string) {
  var index = 1;
  var remainingLetters = string.length - 1;
  var frequencies = {};
  var splitString = string.split("");
  var sortedStringLetters = string.split("").sort();

  sortedStringLetters.forEach(function(val, i) {
    if (!frequencies[val]) {
      frequencies[val] = 1;
    } else {
      frequencies[val]++;
    }
  })

  function factorial(coefficient) {
    var temp = coefficient;
    var permutations = coefficient;
    while (temp-- > 2) {
      permutations *= temp;
    }
    return permutations;
  }

  function getSubPermutations(object, currentLetter) {
    object[currentLetter]--;
    var denominator = 1;
    for (var key in object) {
      var subPermutations = factorial(object[key]);
      subPermutations !== 0 ? denominator *= subPermutations : null;
    }
    object[currentLetter]++;
    return denominator;
  }

  var splitStringIndex = 0;
  while (sortedStringLetters.length) {
    for (var i = 0; i < sortedStringLetters.length; i++) {
      if (sortedStringLetters[i] !== splitString[splitStringIndex]) {
        if (sortedStringLetters[i] !== sortedStringLetters[i+1]) {
          var permutations = factorial(remainingLetters);
          index += permutations / getSubPermutations(frequencies, sortedStringLetters[i]);
        } else {
          continue;
        }
      } else {
        splitStringIndex++;
        frequencies[sortedStringLetters[i]]--;
        sortedStringLetters.splice(i, 1);
        remainingLetters--;
        break;
      }
    }
  }
  return index;
}

anagramPosition("ARCTIC") // => 42

I didn't comment the code but I did try to make the variable names as explanatory as possible. If you run it through a debugger process using your dev tools console and throw in a few console.logs you should be able to see how it uses the formula in the above-linked S.O. post.