3

Given a string, you can find the lexicographic rank of the string using this algorithm:

Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters and 4 of them are smaller than ‘S’. So there can be 4 * 5! smaller strings where first character is smaller than ‘S’, like following

R X X X X X

I X X X X X

N X X X X X

G X X X X X

Now let us Fix S and find the smaller strings staring with ‘S’.

Repeat the same process for T, rank is 4*5! + 4*4! +…

Now fix T and repeat the same process for R, rank is 4*5! + 4*4! + 3*3! +…

Now fix R and repeat the same process for I, rank is 4*5! + 4*4! + 3*3! + 1*2! +…

Now fix I and repeat the same process for N, rank is 4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…

Now fix N and repeat the same process for G, rank is 4*5! + 4*4 + 3*3! + 1*2! + 1*1! + 0*0!

Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597

Since the value of rank starts from 1, the final rank = 1 + 597 = 598

I would like to know how to find the rank if the string contains duplicate characters. When to divide by factorial of repeated occurrences ?

crisron
  • 115
vaidy_mit
  • 631

2 Answers2

5

There's a similar process, complicated by counting permutations of strings with duplicates. For example, the number of permutations of AAABB is $5!/3!2!$.

With that in mind, here's how we could find the rank of BCBAC. We count the smaller permutations $s$ by considering the first position where $s$ is smaller. For example, if it's position 1, $s$ looks like A followed by a permutation of the remaining letters {BBCC}, of which there are $4!/2!2!$.

1: A + {BBCC} $\to$ 4!/2!2!

2: BB + {ACC} $\to$ 3!/1!2!, BA + {BCC} $\to$ 3!/1!2!

3: BCA + {BC} $\to$ 2!/1!1!

4: BCB? (not possible) $\to$ 0

So the answer is 6 + (3 + 3) + 2 + 0 = 14.

Hew Wolff
  • 4,074
3

If there are k distinct characters, the i^th character repeated n_i times, then the total number of permutations is given by

              (n_1 + n_2 + ..+ n_k)!
   ------------------------------------------------ 
                n_1! n_2! ... n_k!

which is the multinomial coefficient. Now we can use this to compute the rank of a given permutation as follows:

Consider the first character(leftmost). say it was the r^th one in the sorted order of characters.

Now if you replace the first character by any of the 1,2,3,..,(r-1)^th character and consider all possible permutations, each of these permutations will precede the given permutation. The total number can be computed using the above formula.

Once you compute the number for the first character, fix the first character, and repeat the same with the second character and so on.

C++ code for handling strings with duplicates https://ideone.com/qXxuVJ

Shubham Nanda
  • 31