Find lexicographic rank of a given string

Problem statement:- Program to Find the lexicographic rank of a given string.

Example:-

              Input: Given

                                 String=cat

             Output: 3

Explanation:  All Permuntation of the string are 

                    /*act(Rank 1) atc(Rank 2) cat(Rank 3) cta(Rank 4) tac(Rank 5) tca(Rank 6) */

Data requirement:-

   Input Data:- str

  Output Data:-rank

  Additional Data:- in, len, fact, count, i

Program in C

Here is the source code of the C Program to Find the lexicographic rank of a given string.

Code:

#include<stdio.h>

#include<string.h>

int Find_Factorial(int len)

{

    int fact=1,i;

    for(i=1;i<=len;i++)

        fact=fact*i;

    return fact;

}

int Find_Lexicographic_Rank(char str[], int len)

{

    int rank=1,in,out;

    for(in=0;in<len;in++){

        int count=0;

    for(out=in+1;out<=len;out++)

    {

        if(str[in]>str[out])

            count++;

    }

    rank+=count*Find_Factorial(len-in);

    }

    return rank;

}

main()

{

    char str[100]={0};

    int count=0;

    printf("Enter your String:");

    gets(str);

    printf("Lexicographic Rank of given String is: %d", Find_Lexicographic_Rank(str,strlen(str)-1));

}

Input/Output:

Enter your String:cat

Lexicographic Rank of given String is: 3

Program in C++

Here is the source code of the C++ Program to Find the lexicographic rank of a given string.

Code:

#include<iostream>

#include <cstring>

using namespace std;

int Find_Factorial(int len)

{

    int fact=1,i;

    for(i=1;i<=len;i++)

        fact=fact*i;

    return fact;

}

int Find_Lexicographic_Rank(string str, int len)

{

    int rank=1,in,out;

    for(in=0;in<len;in++){

        int count=0;

    for(out=in+1;out<=len;out++)

    {

        if(str[in]>str[out])

            count++;

    }

    rank+=count*Find_Factorial(len-in);

    }

    return rank;

}

main()

{

    string str;

    cout<<"Enter your String:";

    getline(cin,str);

    int len=0,in,count=0;

    for(in=0;str[in]!='\0';in++)

    {

        len++;

    }

    cout<<"Lexicographic Rank of given String is: "<<Find_Lexicographic_Rank(str,len-1);

}

Input/Output:

Enter your String:tca

Lexicographic Rank of given String is: 6

Program in Java

Here is the source code of the Java Program to Find the lexicographic rank of a given string.

Code:

import java.util.Scanner;

public class LexicographicRank {

static int Find_Factorial(int len)

{

    int fact=1,i;

    for(i=1;i<=len;i++)

        fact=fact*i;

    return fact;

}

static int Find_Lexicographic_Rank(String str, int len)

{

    int rank=1,in,out;

    for(in=0;in<len;in++){

        int count=0;

    for(out=in+1;out<=len;out++)

    {

        if(str.charAt(in)>str.charAt(out))

            count++;

    }

    rank+=count*Find_Factorial(len-in);

    }

    return rank;

}

public static void main(String[] args) {

Scanner cs=new Scanner(System.in);

String str;

System.out.println("Enter your String:");

str=cs.nextLine();

System.out.print("Lexicographic Rank of given String is: "+Find_Lexicographic_Rank(str,str.length()-1));

cs.close();

}

}

Input/Output:

Enter your String:

abca

Lexicographic Rank of given String is: 4

Program in Python

Here is the source code of the Python Program to Find the lexicographic rank of a given string.

Code:

def Find_Factorial(len1):

    fact = 1

    for i in range(1, len1+1):

        fact = fact * i

    return fact

def Find_Lexicographic_Rank(str,len1):

    rank = 1

    for inn in range(0, len1):

        count=0

        for out in range(inn+1, len1+1):

            if str[inn] > str[out]:

                count+=1

        rank+=count*Find_Factorial(len1-inn)

    return rank

str=input("Enter Your String:")

print("Lexicographic Rank of given String is: ",Find_Lexicographic_Rank(str,len(str)-1))

Input/Output:

Enter Your String:right

Lexicographic Rank of given String is:  85

More:-

C/C++/Java/Python Practice Question