Rank of a permutation

Problem:
Given a word consisting of letters, different words can be formed using all the letters in the word. Find the rank of input word in sorted list of all possible words.

Eg.
ABAB = 2
QUESTION = 24572

Program should use no more than 1GB memory and run within 500 milliseconds. Maximum input length = 25 and input word will contain atleast 2 different letters.

Solution:
From http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation :

A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items. For our purposes the ranking will assign integers 0..(n! − 1) to an ordering of all the permutations of the integers 0..(n − 1).

For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:

  PERMUTATION      RANK
  (0, 1, 2, 3) ->  0
  (0, 1, 3, 2) ->  1
  (0, 2, 1, 3) ->  2
  (0, 2, 3, 1) ->  3
  (0, 3, 1, 2) ->  4
  (0, 3, 2, 1) ->  5
  (1, 0, 2, 3) ->  6
  (1, 0, 3, 2) ->  7
  (1, 2, 0, 3) ->  8
  (1, 2, 3, 0) ->  9
  (1, 3, 0, 2) -> 10
  (1, 3, 2, 0) -> 11
  (2, 0, 1, 3) -> 12
  (2, 0, 3, 1) -> 13
  (2, 1, 0, 3) -> 14
  (2, 1, 3, 0) -> 15
  (2, 3, 0, 1) -> 16
  (2, 3, 1, 0) -> 17
  (3, 0, 1, 2) -> 18
  (3, 0, 2, 1) -> 19
  (3, 1, 0, 2) -> 20
  (3, 1, 2, 0) -> 21
  (3, 2, 0, 1) -> 22
  (3, 2, 1, 0) -> 23

Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).

One use of such algorithms could be in generating a small, random, sample of permutations of n items without duplicates when the total number of permutations is large. Remember that the total number of permutations of n items is given by n! which grows large very quickly: A 32 bit integer can only hold 12!, a 64 bit integer only 20!. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.

Code in Java:

  public static BigInteger getRank(int[] permutation)
  {
    int n = permutation.length;
    BitSet usedDigits = new BitSet();
    BigInteger rank = BigInteger.ZERO;
    for (int i = 0; i < n; i++)
    {
      rank = rank.multiply(BigInteger.valueOf(n - i));
      int digit = 0;
      int v = -1;
      while ((v = usedDigits.nextClearBit(v + 1)) < permutation[i])
        digit++;
      usedDigits.set(v);
      rank = rank.add(BigInteger.valueOf(digit));
    }
    return rank;
  }
 
  public static int[] getPermutation(int n, BigInteger rank)
  {
    int[] digits = new int[n];
    for (int digit = 2; digit <= n; digit++)
    {
      BigInteger divisor = BigInteger.valueOf(digit);
      digits[n - digit] = rank.mod(divisor).intValue();
      if (digit < n)
        rank = rank.divide(divisor);
    }
    BitSet usedDigits = new BitSet();
    int[] permutation = new int[n];
    for (int i = 0; i < n; i++)
    {
      int v = usedDigits.nextClearBit(0);
      for (int j = 0; j < digits[i]; j++)
        v = usedDigits.nextClearBit(v + 1);
      permutation[i] = v;
      usedDigits.set(v);
    }
    return permutation;
  }

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=21500666
http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation
http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms/1506337#1506337