Lexicographic Rank Of A String In C++

Input: string = "cab"
Output: 5

Create a recursive function to calculate the factorial of a given number.
    fact(num):
        if num <= 1:
            return 1 return num * fact(num- 1)
    
Create a function that computes the rank of a string in lexicographic permutation order.
    find_Rank(st):
       Determine the length of the provided string.
        
 Set the rank to 1 at the start.
         Loop through the string's characters one by one.
         Create a variable to count the number of characters smaller than st[i].
         After st[i], loop over the characters.
         Update the rank based on the number of characters less than st[I].
Return the rank of the input string.

#include <bits/stdc++.h>
using namespace std;

// Create a recursive function to calculate the factorial for a given number.
int fact(int num) {
	//Initializing the base condition
	if(num <= 1) {
		return 1;
	}
	// Recursive case: return the number of times the factorial with a value of num-1.
	return num * fact(num - 1);
}

// Create a function that computes the rank of a string in lexicographic permutation order.
int findRanks(string str) {
	//Determine the length of the input string
	int num = str.length();
	// initialising the rank as 1
	int ranks = 1;
	// Every single character in the string is looped through.
	for(int i = 0; i < num; i++) {
		// Create a variable to count the number of characters smaller than str[i].
		int c = 0;

		// After str[I], loop over each character. 
		for(int j = i + 1; j < num; j++) {
			// If str[i] is higher than str[j], the count variable is increased.
			if(str[i] > str[j]) {
				c++;
			}
		}

		//The rank should be updated depending on the number of characters less than str[I] 
		// multiplied by the factorial corresponding to the number of available characters.
		ranks += c * fact(num - i - 1);
	}

	// The highest possible rank of the supplied string is returned.
	return ranks;
}
// Mail section
int main() {
	// defining the given input string
	string strs = "student";
	// Use the findRank function to find the position at the top of the test text and print the result.
	cout << findRanks(strs) << endl;
	//return 0 indicates that the program was completed.
	return 0;
}

+=// C++ Program for finding the lexicographic order of the string
#include <bits/stdc++.h>
using namespace std;

//A utility function for calculating the factorial of the number
int facts(int num) { 
	return (num <= 1) ? 1 : num * facts(num - 1); 
}
// A utility function for counting the smaller characters to the right of the array[low].
int findtheSmallerInRight(string strs, int l, int h)
{
	int countRights = 0, i;

	for (i = l+ 1; i <= h; ++i)
		if (strs[i] < strs[l])
			++countRights;

	return countRights;
}

// A function for determining the rank of a string in all character combinations. 
int findtheRanks(string str)
{
	int length = str.size();
	int muls = facts(length);
	int ranks= 1;
	int countRights;

	int i;
	for (i = 0; i < length; ++i) {
		muls /= length - i;

		////Count the number of characters less than str[i] // from str[i+1] to str[length-1]
		countRights = findtheSmallerInRight(str, i, length - 1);

		ranks countRights * muls;
	}

	return ranks;
}

// Driver code
int main()
{
	string strs= "student";

	// Function calling
	cout << findtheRanks(strs);
	return 0;
}

//Program for finding the rank of a string using Linear Time complexity
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256

// a function for finding the factorial of a number
int fact(int num) { 
	return (num <= 1) ? 1 : num * fact(num- 1); 
}

// Create a count array with a value at each index.
// includes the number of smaller characters in the entire string
void populateAndIncreasingCount(int* c, string st)
{
	int i;

	for (i = 0; st[i]; ++i)
		++c[st[i]];

	for (i = 1; i < MAX_CHAR; ++i)
		c[i] += c[i - 1];
}

///Removes a character ch from the count[] array, which was created by populateAndIncreasingCount().
void updatecount(int* c, char ch)
{
	int i;
	for (i = ch; i < MAX_CHAR; ++i)
		--c[i];
}

 //A function for determining the rank of a string in all permutations of individual characters.
int findRanks(string st)
{
	int length = st.size();
	int muls = fact(length);
	int ranks = 1, i;

	//initialising with 0
	int c[MAX_CHAR] = { 0 };

	// Fill up the count array so that c[I] 
	// includes the count of characters in st 
	//that have a value less than i.
	populateAndIncreasingCount(c,st);

	for (i = 0; i < length; ++i) {
		muls /= length - i;

		
		ranks += c[st[i] - 1] * muls;

		//reducing the count
		updatecount(c, st[i]);
	}

	return ranks;
}

int main()
{
	string st = "student";

	// function calling
	cout << "The rank of the string is  "<<findRanks(st);
	return 0;
}

The rank of the string is 2617