×

Search anything:

# Lexicographic rank of string

#### String Algorithms Algorithms We will see what is the rank of the string in lexicographic order, for the words which can be made using all the characters of the given string and calculate using a string algorithm.

# What is lexicographic rank of the string??

Suppose, we are given a string "BAR" and we need to find its lexicographic rank then, what we can do is write down all the lexicographic permutations of that string and then, the position at which this string "BAR" appears will be the lexicographic rank of that string.

For e.g.:- All the permutations of "BAR" in lexicographic order are:-
ABR
ARB
BAR
BRA
RAB
RBA
where, we can see that the string "BAR" appears at the third place and hence, the lexicographic rank of "BAR will be 3.

# How to find lexicographic order of the string?

One way is to find, all the lexicographic permutations and then also capture the position of every lexicographic permutation, and to match the given string with every possible permutation, the positon at whic it matches the given string is the lexicographic rank of the string.
Only problem with this solution is that it is not feasible, as its time complexity is in the order of factorials.

## ALgorithm:

1. Find lexicographic permutation of the string.
2. Place a counter variable which counts all the permutations.
3. Check whether string whose lexicographic rank is to be found out matches the permutation generated.
4. If yes, then print that position and return from the function.

## Implementation:-

``````# Part of OpenGenus
global permuted_array
permuted_array=[]
#count is our array to store the index for permutations of various length.
global count
#Position is the variable to count the lexicographic rank of the string
position=0
#function to calculate the permutations.
def permute(remaining,test_string):
if len(remaining)==1:
return remaining
for i in range(0,len(remaining)):
#We splice the strings to get substrings which further will be reduced.
string=remaining[0:i]+remaining[i+1:len(remaining)]
#Recurring the spliced string to generate shorter strings.
permuted=permute(string,test_string)
# Base case.
if(len(permuted)==1):
# Concatenate the strings
permuted_array.append(remaining[i]+permuted)
else:
j=len(permuted_array[-1])#To find the length of the shortest length string in the permuted_array at any given time as modifications will be done to only those strings.
for k in permuted_array:
if(len(k)!=j):
continue
else:
#Concatenating the required substrings.
permuted_array[count[len(remaining)-1]]=remaining[i]+permuted_array[count[len(remaining)-1]]
if(len(test_string)==len(permuted_array[count[len(remaining)-1]])):
global position
position+=1
if(test_string==permuted_array[count[len(remaining)-1]]):
print("Lexicographic rank of the string is:",position)
return 0

count[len(remaining)-1]+=1
return 0
test_string=input("Enter the string")
#sorting the input string, as only then we will be able to find out the lexicographic order using this algp, otherwise it will just print permutations irrespectove of lexicographic order.
string = ''.join(sorted(test_string))
count=[len(string)]
for i in range(0,len(string)):
count.append(0)
permute(string,test_string)
print(permuted_array)
``````

# Complexity:-

Time complexity is `O(n* n!) `, as our time complexity will be of the form T(n)= n! + n* n! + (n-1)* (n-1)! + (n-2)* (n-2)! +... 1! , which will amount to T(n)= n! + (n+1)! -1! , as n* n! + (n-1)* (n-1)! + (n-2)* (n-2)! +... 1! = (n+1)! -1!. Thus, T(n) = n! + (n+1)! = n!+ (n+1)* n! = n* n! + 2* n!.
Thus, T(n) = n * n!.
Space complexity is `O(n!) ` as we require an array to store all the permutations.

# Solution using Fundamental Principle of Counting:-

## Algorithm:-

In this algorithm we simply apply the Fundamental Principle of Counting which simply states that if there are n ways of doing something and m ways of doing another thing, then there are n* m ways of doing both these actions.
1.Suppose, again we need to find the positon of "BARE" using this algorithm then what we will be doing is firstly sorting the string, hence upon sorting we get "ABER".
2. We compare the first letter of the original string with the letters of the sorted string and we simply add the number of different permutations which can be made with remaining letters of the sorted string, when letters of the sorted string is fixed at the first position, till we don't get the letter which is equal to the first letter of the original string.
3. Once, we get that we simply move to the second letter of the original string amd we compare it with all the letters of the sorted string except the one which has already been matched and add the number of different permutations which can be made with remaining letters to the rank variable.
4. We continue doing this till we don't get the letter matching with the second letter.
5. Similarly doing this with all the other posiitions of the original sring we get the rank of the string.

### For e.g.:

Now, we move to the final letter of the original string which is "B", and since we have to skip "A" as it has already been used our last letter gets matched with second letter of the sorted string and we add 1 to the rank and that will be our lexicographic position of that string.

## Implementation:-

``````import math
a=5
string= input("Enter the string")
sorted_string = ''.join(sorted(string))
length=len(string)
i=0
j=0
rank=0
array=[]
while(j!=length-1):
if(string[j]!=sorted_string[i]):
if(sorted_string[i] in array):
i+=1
continue
rank+=math.factorial(length-j-1)
i+=1
else:
array.append(string[j])
j+=1
i=0
print("Lexicographic rank of the string is:",rank+1)
``````

# Complexity:-

• Worst case time complexity: `O(n * n)`
• Average case time complexity: `O(n * n)`
• Best case time complexity: ` O(n) `
Space complexity is ` O(n) `.

## Question

#### Find the lexicographic rank of "CAB".

5
1
3
4
Using any of the abov algorithm we can find its position.

With this article at OpenGenus, you must have the complete idea of Lexicographic rank of string.