Permutation Index
by Isai Damier

/***************************************************************************
 * Author: Isai Damier
 * Title: Permutation Index
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *  Given a permutation of a set, return the index of the permutation.
 *
 * Sample Input: {3, 1, 2}
 * Sample Output: 4
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n^2)
 * Space Complexity of Solution:
 *   Best = Average = Worst = O(1)
 *
 * Details:
 *   A permutation is an ordering of the elements of a set. So for a set
 *   constituted of the elements 1,2,3; then {1,2,3} and {2,1,3} are two
 *   different permutations of the set. A set of length n has n! permutations.
 *   For example, if a set contains 3 elements, it has 3! = 3*2*1 = 6
 *   permutations. The following algorithm uses the relation between 
 *   permutation and factorial to find the index of a given permutation
 *   of a set.
 *
 *   Illustrating by manually getting the index of {2, 4, 3, 1}.
 *   Since this is a 4-element set, we know there are 4! permutations
 *   (4! = 4*3*2*1). If the set only had 3 elements, we would have 3*2*1
 *   permutations. If the set only had 2 elements, we would have 2!=2*1 
 *   permutations; and so on.
 *
 *   ASIDE: The decimal system of counting is a positional system.
 *   A 3-element decimal number, for instance, has the following three
 *   positional weights: hundred, ten, unit. Hence, we know the value of the
 *   number 472 because we understand: 4*hundred + 7*ten + 2*unit.
 *
 *   If we treat our 4-element set as a positional system, then we get the
 *   following positional weights: 3!, 2!, 1!, 0. So that the index of
 *   {2, 4, 3, 1} is: x*3!+y*2!+z*1!+w*0. Presently it suffices to find the
 *   values of x,y,z to calculate the index (we ignore w because it is paired
 *   with 0). x,y,z are counters: the number of succeeding elements less than
 *   the element being considered. For example, in {2, 4, 3, 1}, there are
 *   two succeeding elements less than 4 (namely 3 and 1). For 2 it's 1 (1);
 *   for 4 it's 2 (3 and 1); for 3 it's 1 (1); for 1 it's 0.
 *
 *   Now we can calculate the index of {2, 4, 3, 1} as: x=1, y=2, z=1:
 *   x*3!+y*2!+z*1!+w*0 = 1*3! + 2*2! + 1*1! = 6 + 4 + 1 = 11.
 *
 *   Now that we have our algorithm, the trick is implementing it. As you
 *   may imagine there are a number of possible implementations. The
 *   presented implementation focuses on using constant auxiliary memory:
 *   memory = O(1) and time = O(n^2). The code is written for readability.
 **************************************************************************/ 
 public int permutationIndex(int[] permutation) {
  int index = 0;
  int position = 2;// position 1 is paired with factor 0 and so is skipped
  int factor = 1;
  for (int p = permutation.length - 2; p >= 0; p--) {
    int successors = 0;
    for (int q = p + 1; q < permutation.length; q++) {
      if (permutation[p] > permutation[q]) {
        successors++;
      }
    }
    index += (successors * factor);
    factor *= position;
    position++;
  }
  return index;
}
import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

  /**
   * Test of permutationIndex method, of class Numbers.
   */
  @Test
  public void testPermutationIndex() {
    System.out.println("permutationIndex");
    int[][] three = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1},
      {3, 1, 2}, {3, 2, 1}};
    Numbers instance = new Numbers();
    for (int i = 0; i < three.length; i++) {
      assertEquals(i, instance.permutationIndex(three[i]));
    }

    int[][] four = {{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2},
                        {1, 4, 2, 3}, {1, 4, 3, 2},

      {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3, 4, 1}, {2, 4, 1, 3},
                        {2, 4, 3, 1},

      {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 4, 1}, {3, 4, 1, 2}, 
                        {3, 4, 2, 1},

      {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3}, {4, 2, 3, 1}, {4, 3, 1, 2},
                        {4, 3, 2, 1}};

    for (int i = 0; i < four.length; i++) {
      assertEquals(i, instance.permutationIndex(four[i]));
    }
  }
}