UVA 941 PERMUTATION

Rank of a  given String - In a Lexicographic taste- 
Lexicographic style deals with dictionary style arrangement of characters.
The Rank of a particular arrangement  of characters of a string pretains to a particular permutation adhering to lexicographic arrangement

Taking an example of a given string "abc" , the rank of "abc" would be 1 - lexicographically
Similarly-
abc = 1
acb = 2
cba = 6

The simplest solution that strikes in mind is to take out all lexicographic permutation of the given string and then 
iterate over all permuataions until we find our given match , incrementing passing by every term.

This solution can make complexity increasing exponentially in worst case  :P


The efficient solution is  somewhat tricky , just some high school math work- 
Let the given string be " JIM"  
Check first character "J"  
Total characters = 5
Character smaller then "J" = "I" i.e 1
So there can be 1*2! strings , which have first character smaller then "J" - 
IXX

Now fixing "J" we gotta find smaller strings  starting with "J"
Next character "I" have no character smaller then itself so zero in this case with total rank 1*2!+ 0*1!+...
Next character "M"  have no character smaller then itself so zero in this case with total rank 1*2!+ 0*1!+0*1!..

So rank = 1*2!+ 0*1!+0*0!= 2
As rank starts from 1 unlike numbering starting from zero in programming so rank of "JIM" = 2+1= 3

NOTE- 
To calculate the Lexicographic permuatation for repeated characters, just follow same procedure and in end divide the rank with p! where p is count of occurence of each repeated character . eg-  rank/2! in case of  string  "JIMMY "

//******************* codebloodedvalley.blogspot.com *********************
// ******************  1:24 AM  03-03-2014, GNDU RC SATHIALA *************
#include<stdio.h>
#include<string.h>
#define MAX_CHAR 256

// utility function to find n factorial
int fact(int n){
return (n<=1) ? 1 : n * fact(n-1) ; 
}

// an array count where value at each index gonna 
// contain total count of smaller characters present in given string

void  increaseCountbyPopulating (int* count ,  char* str){
int i;
for(i=0;str[i];++i) // populating  count of each character
++count[ str[i] ];

// instead of calling a loop again n again to check the total characters smaller then particular 
//character present , just iterate once and add the preceding value in every next count[i] for  i <=256
// This will help us to straightway accessing the total numbers of of character smaller then count[str[i]] as shown
// later in the rankFinder() . 
// Unexpected , but Dont panic :D

for(i=1;i<256;++i)  
count[i]+=count[i-1];


}
void countUpdate(int* count, char ch){        // this function is fixing the value of character as explained above
// by deleting its every  occurence in count[] 
int i;
for(i=ch;i<MAX_CHAR;++i)
--count[i];


}

//  now checkout the function to find the rank,pretty simple, understand afformentioned point carefully 
int rankFinder(char* str){
int len =  strlen(str);
int mul = fact(len);
int rank = 1, i;

int count[MAX_CHAR] = {0}; // initialising all elements to 0

 // populating count[i] having count of characters smaller then i present in given string
 increaseCountbyPopulating(count,str);
  for (i = 0; i < len; ++i)
    {
        mul /= len - i;  // this is tricky and efficient, simple high school maths

        // count number of chars smaller than str[i]
        // from str[i+1] to str[len-1]
        rank += count[ str[i] - 1] * mul;

        // Reduce count of characters greater than str[i], i.e fixing the occurence of string[i]
        countUpdate (count, str[i]);
    }

    return rank;
}

// Driver program 
int main()
{
    char str[] = "JIM";
int rank= rankFinder(str);  
printf ("%d", rank);
    return 0;
}