CareerCup

This is the "Rank of a permutation" algorithm. It is discussed here:
rosettacode.org/wiki/Permutations/Rank_of_a_permutation

BigInteger[] fact;
	
	BigInteger getRank(String word) {
		int n = word.length();
		computeFact(n - 1);
 
		char[] letterArray = word.toCharArray();
		Arrays.sort(letterArray);
		ArrayList<Character> letterList = new ArrayList<Character>();
		
		for (int i = 0; i < n; i++){
			char c = letterArray[i];
			letterList.add(c);
		}
		 
		BigInteger rank = BigInteger.ONE;
		
		for (int i = 0; i < n - 1; i++){
			Character c = word.charAt(i);
			int index = letterList.indexOf(c);

			BigInteger rawDiv = BigInteger.ONE;
			int repeat = 1;
			for (int j = 1; j < letterList.size(); j++){
				if (letterList.get(j).equals(letterList.get(j - 1))){
					repeat++;
				}
				else{
					rawDiv = rawDiv.multiply(fact[repeat]);
					repeat = 1;
				}
			}
			rawDiv = rawDiv.multiply(fact[repeat]);
			
			BigInteger count = BigInteger.ZERO;
			repeat = 1;
			for (int j = 1; j <= index; j++){
				if (letterList.get(j).equals(letterList.get(j - 1))){
					repeat++;
				}
				else{
					if (repeat == 1){
						count = count.add(fact[n - 1 - i].divide(rawDiv));
					}
					else{
						count = count.add(fact[n - 1 - i].multiply(BigInteger.valueOf(repeat)).divide(rawDiv));
					}
					repeat = 1;
				}
			}
			
			//System.out.println(i + " " + count);
			rank = rank.add(count);
			letterList.remove(index);
		}

	    return rank;
	}

	void computeFact(int n) {
	    
		fact = new BigInteger[n + 1];
		fact[0] = BigInteger.ONE;
	    for (int i = 1; i <= n; i++)
	        fact[i] = fact[i - 1].multiply(BigInteger.valueOf(i));

	}

Here's my code for rank of string with all distinct characters..
Description:
freq(char *str, int len, int* count/*assumed to be of len=26*/): counts the frequency of each char present in the string. As per my assumption each char count must be 1.
factorial(int n): finds factorial of given n.
int countLessThan(char c, int *freq) : counts number of characters which are less than char c
ull findRank(char *str, int len, int pos, int* count): actually finds the rank of given word.
ull wordRank(char *str, int len): wrapper around findRank(). Just to supply the count[] array
void wordRankDriver(): main driver function.

IDEA: The idea is to calculate the rank of given word, find the number of permutations which are rank wise smaller than current word. To do so, permutation is calculated recursively.
1. Take all the chars which are smaller than char at position: pos=0. Now each of smaller char can be placed at pos 0 and rest (total # of chars -1) can be arranged among themselves in factorial((total # of chars -1) ways.
2. Once this is calculated for current position: pos, increment pos by 1 and calculate recursively # of permutations for next pos, that is pos.

Hope this description makes it somewhat clear. Appologies if not able to describe the procedure clearly.

BIG ASSUMPTION: All characters in the word are unique with no repeated chars.

#include<iostream>
#include<cstring>

using namespace std;

typedef unsigned long long ull;

void freq(char *str, int len, int* count/*assumed to be of len=26*/)
{
	memset(count, 0x00, 26*sizeof(int));
	if(!str || len == 0)
		return ;
	for(int i=0; (str[i]!= '\0') && (i < len); i++)
		count[tolower(str[i])-'a']++;
	return ;
}

ull factorial(int n)
{
	ull fact = 1;
	for(int i=2; i <= n; i++)
		fact *= i;
	return fact;
}

int countLessThan(char c, int *freq)
{
	int count=0;
	for(int i =0; i<c-'a'; i++)
		count += freq[i];
	
	return count;
}

//ASSUMPTION: All characters in the word are unique with no repeated chars.
ull findRank(char *str, int len, int pos, int* count)
{
	if(!str || len == 0)
		return 0;
	if(pos == len-1)
		return 1;
	int rank = countLessThan(str[pos], count);
	rank = rank*factorial(len-pos-1);
	count[tolower(str[pos])-'a']--;
	return rank + findRank(str, len, pos+1, count);
}

ull wordRank(char *str, int len)
{
	int count[26] = {0,};
	freq(str, len, count);
	return findRank(str, strlen(str), 0, count);
}

void wordRankDriver()
{
	ull rank = wordRank("question", strlen("question"));
	cout << "Rank of word question  = " << rank << endl;

	rank = wordRank("einoqstu", strlen("question"));
	cout << "Rank of word einoqstu  = " << rank << endl;

	rank = wordRank("education", strlen("education"));
	cout << "Rank of word education  = " << rank << endl;
}

Here's a solution in Java that can handle words with repeated characters. The real solution should use BigInteger instead of int to accommodate factorials over 12!.

int rank(String word) {
    List<Character> chars = new ArrayList<>();
    Map<Character, Integer> freqs = new HashMap<>();

    for (char c : word.toCharArray())
        chars.add(c);

    Collections.sort(chars);

    for (Character c : chars)
        if (freqs.containsKey(c))
            freqs.put(c, freqs.get(c) + 1);
        else
            freqs.put(c, 1);

    int rank = 1;
    
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        int sortPos = Collections.binarySearch(chars, c);
        int wordLength = chars.size();
        rank += sortPos * possibilities(wordLength, freqs) / wordLength;
        chars.remove(sortPos);
        freqs.put(c, freqs.get(c) - 1);
    }

    return rank;
}

int possibilities(int wordLength, Map<Character, Integer> freqs) {
    int possibilities = fact(wordLength);
    for (Map.Entry<Character, Integer> entry : freqs.entrySet())
        possibilities /= fact(entry.getValue());
    return possibilities;
}

int fact(int n) {
    int fact = 1;

    for (int i = 2; i <= n; i++)
        fact *= i;

    return fact;
}

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;


public class AnagramCount {
static Map<Integer, BigInteger> factMap = new TreeMap<Integer, BigInteger>();
static BigInteger count = BigInteger.ZERO;

/**
* @param args
* Performs
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter the input");
Scanner sc = new Scanner(System.in);
String inputString = sc.next();
long startTime = System.currentTimeMillis();
findPermutations(inputString);
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Run Time (in milliseconds) : " + totalTime);
}

/*
* Modification of Bell's Algorithm for permutation. But does not form words at every step
* Calculates the number of words that could be formed until the required permutation of words is reached
* Worst Case RunTime Complexity : O(n * n) - Performs n iterations for fixing each character that could match the input String
* Worst Case Space Complexity : O(n) -linear with n - to track factorial values and duplicates
* where 'n' is the length of the input String
*/

public static void findPermutations(String inputString){
char[] word = inputString.toCharArray();
Arrays.sort(word);
int i = 0;
int j = 0;
while(i<word.length){
if(word[i] != inputString.charAt(j)){
count = count.add(countPermutations(word, i));
for(int k=i; k<word.length; k++){
if((int)word[k] > (int)word[i]){
char temp = word[i];
word[i] = word[k];
word[k] = temp;
break;
}
}
}
else if(word[i] == inputString.charAt(j)){
i += 1;
j += 1;
}
}
System.out.println("Index of the word " + inputString + " : " + count.add(BigInteger.ONE).toString());
}

/*
* Gets the word array which contains individual characters and the current position of the string which is fixed
* Finds the possible PERMUTATION OF WORDS WITH THE CHARACTER 'x'(any character) at the start position
*/

public static BigInteger countPermutations(char[] word, int startPosition){
Map<Character, Integer> duplicateCountMap = new HashMap<Character, Integer>();
for(int i = startPosition + 1; i<word.length; i++){
if(duplicateCountMap.get(word[i]) == null){
duplicateCountMap.put(word[i], 1);
}
else{
duplicateCountMap.put(word[i], duplicateCountMap.get(word[i]) + 1);
}
}
BigInteger numerator = factorial(word.length - startPosition - 1);
BigInteger denominator = BigInteger.ONE;
for(Integer value : duplicateCountMap.values()){
denominator = factorial(value).multiply(denominator);
}
return numerator.divide(denominator);
}


/*
* FACTORIAL CALCULATION WITH MEMOIZATION
* Gets the number as input and returns its Factorial value
*/

public static BigInteger factorial(int number){
if(number <= 1)
return BigInteger.ONE;
if(factMap.get(number) == null){
factMap.put(number, BigInteger.valueOf(number).multiply(factorial(number - 1)));
}
return factMap.get(number);
}
}