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

by

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.

More Related Contents:

  1. Algorithm to generate all possible permutations of a list?
  2. Fast permutation -> number -> permutation mapping algorithms
  3. Generate all binary strings of length n with k bits set
  4. Shuffle list, ensuring that no item remains in same position
  5. Algorithm for finding numerical permutation given lexicographic index
  6. Algorithm to list unique permutations of string with duplicate letters
  7. Calculating permutations in F#
  8. Permute all unique enumerations of a vector in R
  9. Algorithm for permutations of operators and operands
  10. Check if array B is a permutation of A
  11. Algorithm to list all unique permutations of numbers contain duplicates
  12. Data structures for loaded dice?
  13. How to determine if a linked list has a cycle using only two memory locations
  14. Computing set intersection in linear time?
  15. Best word wrap algorithm? [closed]
  16. Finding closest neighbour using optimized Levenshtein Algorithm
  17. What is a bubble sort good for? [closed]
  18. Hashing a Tree Structure
  19. Quicksort superiority over Heap Sort
  20. Best way of calculating n choose k?
  21. Finding multiple entries with binary search
  22. Painter puzzle – algorithmic estimation from first principles
  23. Given a number, find the next higher number which has the exact same set of digits as the original number
  24. The best shortest path algorithm
  25. Convert light frequency to RGB?
  26. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  27. Bridges in a connected graph
  28. Breadth First Search and Depth First Search
  29. Portable efficient alternative to PDEP without using BMI2?
  30. Postfix notation to expression tree

Leave a Comment