Lexicographic rank of string


StringViews 2840

Find the lexicographic rank of a string. (string without duplicates)

Example

Input string : “CAB”
Output : Rank is 5

Total possible permutations are : ABC, ACB, BAC, BCA, CAB, CBA(lexicographic order)

Therefore, rank is 5

Time complexity : O(n)

Algorithm

a. Initialize rank = 1.

b. Traverse in the string, for every char find the characters less than it.

c. Add all possible permutations with smaller characters to the rank and return the final rank.

Do this by,

1. Create an auxiliary count array, and store the count of smaller characters in the whole string.

2. For every character count number of characters smaller than string[i] from string[i+1] to string[len-1]

3. After adding it to rank.

4. Reduce count of characters greater than string[i], by removing the current character.

d. Return the final rank.

Algorithm working

Input string : “codes”

Apply algorithm,

Initialize rank = 1,

a) i = 0, character = ‘c’
letters less than c in the right are NULL,
Move forward.

b) i = 1, character = ‘o’
letters less than o in the right are d, e
c d _ _ _  → 3!
c e _ _ _  → 3!
rank = rank + 3! + 3!
rank = 13

c) i = 2, character = ‘d’
letters less than d in the right are NULL
Move forward.

d) i = 3, character = ‘e’
letters less than e in the right are NULL
Move forward.

e) i = 4, character = ‘s’
letters less than d in the right are NULL
End here,
Final rank = 13.
Therefore, rank of “codes” = 13

C++ Program

#include <bits/stdc++.h>

using namespace std;
#define ASCII_VALUES 256
 
//recursive function to find factorial function
int fact(int n)
{
    if (n<=1)
    {
        return 1;
    }
    else
    {
        return n * fact(n-1);
    }
}
//function to store the count of chatcters which are smaller i n the whole string
//stores in count array
void CreateCountArray(int* count, char* string)
{
    int i;
    for(i = 0; string[i]; ++i )
    {
        ++count[ string[i] ];
    }
 
    for( i = 1; i < 256; ++i )
        count[i] += count[i-1];
}
//count array by removing the character ch
void UpdateCountArray(int* count, char ch)
{
    for(int i = ch; i < ASCII_VALUES; ++i )
    {
        count[i] = count[i] - 1;
    }
}
 

int LexicographicRank(char* string)
{
    int len = strlen(string);
    int per = fact(len);
    //Initialize rank = 1 and countarray with zeroes
    int rank = 1;
    int count[ASCII_VALUES] = {0};
    //createcount array
    CreateCountArray(count, string);
    for (int i = 0; i < len; ++i)
    {
        per = per/(len - i);
        rank = rank + (count[ string[i] - 1] * per);
        //update count array by removing the current character
        UpdateCountArray (count, string[i]);
    }
    //return final rank
    return rank;
}
 
//Main function
int main()
{
    char string[] = "codes";
    cout<<LexicographicRank(string);
    return 0;
}

Try It

 

Translate »