CareerCup

Assume it has all distinct characters.
total number of permutations : n!
Algo:
start from first character and traverse till end. find how many characters are ranked before this, suppose this is x, now we know there are x * (n-1)! permutations are ranked above this.
Repeat the procedure for every character in string.

int n = strlen(str);
int rank = 0;
for (i = 0; i < n-1; i++) {
int x=0;
for (j = i+1; j<n ; j++) {
if (str[i] > str[j])
x++;
}
rank = rank+ x*((n-i-1)!)
}

return rank;

Given a string, find its rank among all its permutations sorted lexicographically. For example, rank of “abc” is 1, rank of “acb” is 2, and rank of “cba” is 6.

For simplicity, let us assume that the string does not contain any duplicated characters.

One simple solution is to initialize rank as 1, generate all permutations in lexicographic order. After generating a permutation, check if the generated permutation is same as given string, if same, then return rank, if not, then increment the rank by 1. The time complexity of this solution will be exponential in worst case. Following is an efficient solution.

Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters and 4 of them are smaller than ‘S’. So there can be 4 * 5! smaller strings where first character is smaller than ‘S’, like following

R X X X X X
I X X X X X
N X X X X X
G X X X X X

Now let us Fix S’ and find the smaller strings staring with ‘S’.

Repeat the same process for T, rank is 4*5! + 4*4! +…

Now fix T and repeat the same process for R, rank is 4*5! + 4*4! + 3*3! +…

Now fix R and repeat the same process for I, rank is 4*5! + 4*4! + 3*3! + 1*2! +…

Now fix I and repeat the same process for N, rank is 4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…

Now fix N and repeat the same process for G, rank is 4*5! + 4*4 + 3*3! + 1*2! + 1*1! + 0*0!

Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597

Since the value of rank starts from 1, the final rank = 1 + 597 = 598

1. Find the suffix array SA for the string in O(n) time

int i=0;
int rank =0;
 while (SA[i] !=0)
{
   rank += (SA[i])!;
   i++;

}
rank++;

What we can do is that for example ,the string is god ,
now, if we arrange the letters in lexicographic order, we get d -> g -> o.
but the first letter we need is g.
1)how many letters are there before g , just 1
2)so number of words starting with d are (2! /(1! * 1!) ) (hope you understand this)
now the 3rd word will be starting with g..
and we continue in this manner till we get out string

1) Calculate the length of the string.
2) Create an array str[26], and index being the key increment the value by '1' for each character in the given string.
e.g. gods, str['g'-'a']++, str['o'-'a']++, str['d'-'a']++, str['s'-'a']++.
O(N) time for this step.
3) Traverse the str array (which is now in sorted order of the characters), Starting from rank '1' give rank to each character in the str array.
thus,
str['d'-'a'] = 1
str['g'-'a'] = 2
str['o' - 'a'] = 3
str['s' - 'a'] = 4

4) Final step to calculate the rank of the permutation. Traverse the string again and do the following:

for(int i=0;i<N;i++){
      rank += (str[input[i] - 'a']-1)*(factorial(N-i-1));
//Update the rank of all those characters which are higher in rank than the present.
      for(int j=i+1;j<N;j++){
          if(input[j]>=input[i]) str[input[j]-'a']--;
      }
}

The above can be modified to handle strings with repeated characters as well.

A recursive Solution is presented below.
Taking the same example as above = (god).
god..
# of characters lesser in rank than the first character (g) is 1 (= d)
# of permutations = getCountBefore(g) * (n-1)*(n-2) + getRank(remainder)
remainder in this case is od.
Rank of od is 2 (do , od) .. this is also computed using the same recursive method. we do this until we hit the base case of input string length = 1 at which point we return 1.
So for god, the trace will be
getCountBefore(g in god) * (n-1) * (n-2) [ 1 * (3-1) * (3-2) ] + getRank (od)
for od --> getCountBefore(o in od ) * (n-1) = [ 1 * 1] + getRank (d)
for d (base case) getRank(d) will return 1;
So rank of god will be 2 + 1 + 1 = 4
the java code is presented below

public int getRank(String input) {
		
		int count = getCountBefore(input);
		
		return getRank(input,count);
		
	}

	private int getRank(String input, int count) {
		if (input == null || input.isEmpty()) return 0;
		if (input.length() == 1) return 1;
		
		else {
			int n = input.length();
			String remainder = input.substring(1);
			if (n > 2) {
				return getCountBefore(input)*(n-1)*(n-2) + getRank(remainder,getCountBefore(remainder));
			}
			else {
				return getCountBefore(input) * (n-1) + getRank(remainder, getCountBefore(remainder));
			}
		}
		
		
	}

	private int getCountBefore(String input) {
		if (input == null || input.isEmpty() || input.length() == 1) return 0;
		int count = 0;
		char c = input.charAt(0);
		char[] charArray = input.toCharArray();
		for (int i = 1; i < charArray.length; i++) {
			if(charArray[i] < c) {
				count++;
			}
		}
		return count;
		
	}

public static void main(String[] args) {

System.out.println(rank("adbc") +1);
}

private static int rank(String string) {
int rank = 0;
for(int i = 1; i < string.length(); i++){
if(string.charAt(i) < string.charAt(0)){
rank += fact(string.length() -1);
}
}
System.out.println("rank " + rank);
if(string.length() > 1)
rank += rank(string.substring(1));
return rank;
}

private static int fact(int i) {
if(i == 1)
return 1;
return i * fact(i-1);
}

I took the approach of doing all possible permutations, instead of omitting repeating value strings (i.e. if the string was abc a possible permutation would be aaa, aab, aac, aba,.. etc.)

The first thing was finding a pattern, which came from writing examples for 3 and 4 length char array. Each row from right to left adds the length of the string, say m, to the power of row number, say r (which ends at r=0 at the right most row). Then we multiply this number by the index of the char in a sorted char array, say p.

So the equation would be: m^r * p
ex. {a,c,b} m = 3, we start at the at row 0 which would be in position 0 of the sorted array. so the equation would be: (3^2 * 0) = 0 for a
then row 1 which is c which is in position 2 : (3^1 * 2) = 6
then row 2 which is b, which is in position 1 : (3^0 * 1) = 1

then we add up the values giving us 7
which is the correct index if the series index starts with 0
if you want an index that starts at 1 you have to add 1 to the result.

{a,b,c} (3^2 * 0) = 0, (3^1 * 1) = 3, (3^0 * 2) = 2, += 5 (or 6 if indexing starts at 1).

aaa baa caa
aab bab cab
aac bac cac
aba bba cba
abb bbb cbb
abc bbc cbc
aca bca cca
acb bcb ccb
acc bcc ccc

The last modification is that since we are allowing for a permutations to have duplicate values in the string, we have to also pass in the set of valid letters for the permutation.
So if the string to search for rank was "caa" we also have to pass in {a,c,b} so all the letters are available to do the correct computations.

public static void main(String[] args) {

	System.out.println(rank("acb", "abc")+1);
}

private static int rank(String str, String letters) {
	int rank = 0;		
	char [] set = str.toCharArray();
	char [] sorted = letters.toCharArray();
	Arrays.sort(sorted);
	int size = set.length;
	for(int i = 0; i < size; i++){	
		rank += Math.pow(size, (size-(i+1)))* (Arrays.binarySearch(sorted,set[i]));
	}
	return rank;
}

void permutate(char *a,char *b,char *c,int len1,int len2,int last) // len1==size of the character array //len2==lenth of permutation
{ static int count=0;
for(int i=0;i<len1;i++)
{
if(len2==last)
{
count++;
*(b+len2)='\0';
if(!strcmp(b,c))
{
printf("%d \n",count);
}
return;
}
*(b+len2)=*(a+i);
permutate(a,b,c,len1,len2+1,last);
}
}

We can use the code for getting string in lexicographic order.Whenever we get a string,compare with the string whose rank to be found.Increment a counter if it is greater than the string clacualted.Lastly we will find the rank.

The solutions using n! do not handle repeating char cases elegantly. Below solution does not use n! and handle repeating char cases. The permutation is very time consuming. Hope to see more elegant solution.

int f(char* a, int st, int end)
{
   if(st>end) return 0;

   int r = 0;
   for(int i=st+1; i<=end; ++i)
   {
       if(a[st]>a[i])
       {
          swap(a[i], a[st]);
          r += perm(a, st+1, end);
          swap(a[i], a[st]);
       }
   }

   r += f(a, st+1, end);   

   return r;  
}


int perm(char* a, int st, int end) // permutation
{
   int r=1; // start from 1 to consider the existing one.
   for(int i=st+1;i<=end;++i)
   {
      if(a[st]!=a[i])
      {
          swap(a[st],a[i]);
          r += perm(a, st+1, end);
          swap(a[st],a[i]);      
      }
   }

   return r;
}

C++

int lexicalOrder(vector<int> perm, vector<int>::size_type index) {
	if(perm.size() - 1 == index ) {
		return 0;
	}
	int location = 0;
	for(auto i = index; i < perm.size(); i++) {
		if(perm[i] < perm[index]) location++;
	}
	int block = location * factorial(perm.size() - 1 - index);
	return block + lexicalOrder(perm, index + 1);
}

import java.util.Arrays;

/**
* Created by abhishek on 10/2/17.
*/
public class StringRankMain {

public static void main(String []args)
{
String inputString = "string";
int index = 0;
int rank = 0 ;

String tmpString = inputString;

int length = tmpString.length();

while(length >1)
{

tmpString = mySort(tmpString);
int strLength = tmpString.length();

int permCount = findFactorial(strLength);

int rangeSize = permCount / strLength;

int indexOfChar = tmpString.indexOf(inputString.charAt(index));

indexOfChar++;

int localRank = (rangeSize * (indexOfChar -1)) + 1;
System.out.println("local Rank = " + localRank);
if(rank ==0){
rank = localRank;

}else {
rank += localRank-1;
}


index++;
tmpString=inputString.substring(index);
length = tmpString.length();
}

System.out.println("final Rank = " + rank);
}


static String mySort(String string)
{
char[] chArray = string.toCharArray();
Arrays.sort(chArray);
return new String(chArray);
}

static int findFactorial(int no){
if(no == 1)
return 1;
else
return no * findFactorial(no-1);
}
}

for string "god"..Sort the string --> (nlogn)...lets say string is now "dgo"
start the permutation of "dgo", keep the counter. at the time when the string matches with the original string return the counter !!

Suggestions are welcome !! :)