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.
#======================================================================= 
 def permutationIndex( permutation ):
  index = 0
  position = 2 # position 1 is paired with factor 0 and so is skipped
  factor = 1
  for p in range( len( permutation ) - 2, -1, -1 ):
    successors = 0
    for q in range( p + 1, len( permutation ) ):
      if permutation[p] > permutation[q]:
        successors += 1

    index += ( successors * factor )
    factor *= position
    position += 1

  return index
import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testPermutationIndex( self ):
      three = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
        [3, 1, 2], [3, 2, 1]]
      for i in range( len( three ) ) :
        self.assertEquals( i, algorithm.permutationIndex( three[i] ) )


      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 i in range( len( four ) ) :
        self.assertEquals( i, algorithm.permutationIndex( four[i] ) )