Lexicographic Rank of a Word in C++

Today, we will see how to find the lexicographic rank of a string in C++. The lexicographic rank of a string means the rank of the given string in a list of permutations of the given word in alphabetical order. Let us take an example of say a word, ‘bye’, the various permutations of the letters of the word can be created such as ‘bey’, ‘eby’, ‘ybe’ etc. When we list all these words in alphabetical order, then the rank of the original word, ‘bye’ is called the lexicographic rank of the word.

 

Mathematical Concept

First, let us understand the basic mathematical concept involved in this problem. This problem can be solved manually using permutations and combinations.

Let us take an example string to understand the concept: “word”

When this string is sorted in alphabetical order, it starts with “dorw , “dowr” etc. We need to find how many such strings exist before we get the actual string.

We start with the first letter and see if it matches with the first letter of the actual string. If it doesn’t then we count all the strings possible with that letter in the first position. That is, we keep that letter fixed and find the possible permutations of the rest of the letters. We then change the first letter to the next one in alphabetical order and repeat the same procedure until the first letter matches. Then we leave the first letter and repeat the procedure with the remaining letter. We need to keep adding the number of all possible combinations to get the lexicographic rank of the string.

Let us apply this algorithm for the example :

string : “word”

dorw does not have w in the first position, so we take all the permutations and we will do this thrice until we get w in the first place

no. of permutations with d as first letter = 3! = 6

no. of strings before we get w in the first place = 6 x 3 = 18

Now, consider the second letters keeping the first letters fixed

“word” and  “wdor”

no. of permutations with d as second letter = 2! = 2

total no. of strings before getting wo in the first places = 2+18 = 20

Now the third letters

“word” and “wodr”

no.of permutations = 1! =1

now the total number of permutations to get the string “word” = 20 +1 =21

Therefore, we can say that the lexicographic rank of the string “word” is 21.

For more information regarding the mathematical concept, you can check this article.

Program for lexicographic rank

Let us now implement the above logic as a C++ program.

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
string letters,rnk;
int factorial(int num)                               // the function to calculate the factorial for permutation calculations
{
  if(num==1)
  return 1;
  return num*factorial(num-1);
}
int search_string(char s)                            // the function to find the position of a character in the string
{
  int i;
  for(i=0;i<letters.length();i++)
  {
    if(s==letters[i])
     return i+1;
  }
}
int CountPermutation(string str)                                    // the function calculate the permutaions for repeating and non repeating letters
{
  int countoccur[26] = {0}, len, i, res;
  len = str.length();

                                                               // Count the occurrence of each character.
  for(i = 0; i < len; i++)
  {
    countoccur[str[i]-'a']++;
  }

  res = factorial(len);

                                                                // Divide the length factorial by the factorial of number of occurrence of each character.
  for(i = 0; i < 26; i++)
  {
    if(countoccur[i] > 1)
      res = res/factorial(countoccur[i]);
  }

  return res;
}
int main()
{
  string chk;
  vector<char> ch;
  int i,j,m,count=0,pos;
  cout<<"Enter the letters: ";
  cin>>letters;
  m=letters.length();
  if(m<2)
  {
    cout<<"The word is too short!";
    return 0;
  }
  cout<<"Enter the word for which the rank has to be found: ";
  cin>>rnk;
  sort(letters.begin(),letters.end());
  chk=rnk;
  sort(chk.begin(),chk.end());
  if(!(letters==chk))
  {
    cout<<"The word cannot be formed using the letters!";
    return 0;
  }
while(!letters.empty())                                                    // we use a while loop to go through each character and after calculating the permuations of each 
{ch.clear();                                                               // position we remove that character and do this until the string is empty
pos=search_string(rnk[0]);
for(j=0;j<pos-1;j++)
{chk=letters;
  if(std::count(ch.begin(),ch.end(),chk[j]))
  continue;
  ch.push_back(chk[j]);
  chk.erase(chk.begin()+j);
  count+=CountPermutation(chk);
}
 letters.erase(letters.begin()+pos-1);
 rnk.erase(rnk.begin());
 m--;
}
cout<<++count<<endl;                                                        // the rank of the word is 1 + the number of permutations
system("pause");
return 0;
}

The code accepts two strings as input, where one is the letters for permutations and the other is the target string. Obviously, they both must contain the same letters which, may or may not be in the same order.

Leave a Reply

Your email address will not be published. Required fields are marked *