23

C/C++ Program for Lexicographic rank of a string.

program solution

// C program to find lexicographic rank of a string

#include <stdio.h>

#include <string.h>

 

// A utility function to find factorial of n

int fact(int n)

{

    return (n <= 1) ? 1 : n * fact(n - 1);

}

 

// A utility function to count smaller characters on right of arr[low]

int findSmallerInRight(char* str, int low, int high)

{

    int countRight = 0, i;

 

    for (i = low + 1; i <= high; ++i)

        if (str[i] < str[low])

            ++countRight;

 

    return countRight;

}

 

// A function to find rank of a string in all permutations of characters

int findRank(char* str)

{

    int len = strlen(str);

    int mul = fact(len);

    int rank = 1;

    int countRight;

 

    int i;

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

        mul /= len - i;

 

        // count number of chars smaller than str[i] fron str[i+1] to str[len-1]

        countRight = findSmallerInRight(str, i, len - 1);

 

        rank += countRight * mul;

    }

 

    return rank;

}

 

// Driver program to test above function

int main()

{

    char str[] = "string";

    printf("%d", findRank(str));

    return 0;

}

Output

598