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.:

Again, we need to find the position of "EARB", then firstly we will sort the string which will be "ABER". Now upon comparing the first letter of the original string with the sorted string since they are not equal we add 6 to the value of the rank as that is the number of different words which can be made with "A" fixed at the first position, similarly, upon comparing the second letter of the sorted string with the first letter of original string still they are not equal, hence we again add 6 to the rank but the third letter of the sorted string which is "E", when compared with the first letter of the original string we see that they both are equal and hence, nothing is added on here, and we append the letter "E" in an array whic stores already reached letters of the string, now we reach to the second letter of the original string which is "A" and again compare it with the first letter of the sorted string, since this time it is equal to the first letter, thus, we don't add anything to the rank and again we append A to the array which stores the letters already used, similarly we move to the third position in the string and begin comparing it with the first letter of the string, but, since first letter has already been matched and hence, we skip that and move to the second letter in the sorted string which is "B" and which doesn't match with "R" and hence, we add 1 to the rank as that is the number of permutations which can be formed from the remaining letter, again we compare "R" with "E", but since, it has already been used we skip that and after that we compare it with last letter which is equal to "R" and hence we again don't add anything to the rank and append "R" to the list which stores the reached letters.
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) .

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