Monday, November 19, 2007

Enumerating permutations using inversion vectors and factoradic numbering

Permutations are a fundamental concept in discrete mathematics, and crop up in numerous places in computer science. The set of all possible permutations of n items is usually denoted Sn (since the set forms a group which is isomorphic to the Symmetric group of order n). The number of permutations in this set is n!.

This apparently simple concept poses some unexpected challenges. For instance, the following useful operations are messy to compute via the brute-force way of enumerating successive permutations:
  • List all the permutations in Sn (in lexicographic order)
  • Find the i'th permutation in Sn
This would be straightforward if there was a way of effectively enumerating all permutations; i.e. a mapping between Sn and the integers {1, 2, ..., n!}.

It turns out that this can be done using a pair of ingenious concepts known as the inversion vector and factoradic numbering. These can be used to provide an enumeration of Sn, conveniently in lexicographic order. (Inversion vectors are also known as inversion tables and Lehmer codes - the term vector seems to me to be most appropriate for the nature of the structure.)

A permutation can be written as a sequence of numbers

P = (p1 p2 ... pn) where pi is in {1, 2, ..., n}

An inversion is a pair (pi, pj) where i < j but pi > pj. We define di to be the number of inversions in the sequence where the first element is pi:

di = | { pj : i < j , pi > pj } |

Then the inversion vector for the permutation is the sequence

D = (d1, d2, ..., dn) (di is in the range {0, 1, ..., n-i})

It is fairly straightforward to recover the original permutation from the inversion vector. This paper gives a definition of the forward and reverse mapping algorithms.

There are n! possible sequences D. They are in one-to-one relationship with the set of permutations Sn, and their natural order gives a lexicographic ordering of Sn. So we're halfway to the enumeration that we are looking for.

Inversion vectors can in turn be mapped to the integers in {1, ..., n!} by using the concept of factoradic numbering. A factoradic number is a number made up of a sequence of digits where the radix for digit di is (n-i)!. This Wikipedia article explains the concept in detail.

Here's an example:

P = (4 6 2 5 3 1 8 7) is a permutation in S8.

Its inversion vector is L(P) = [3,4,1,2,1,0,1,0].

The factoradic representation of this is

3×7! + 4×6! + 1×5! + 2×4! + 1×3! + 0×2! + 1×1! + 0×0! = 18175

So inversion vectors and factoradic numbering provide an elegant way of enumerating permutations. But what does this have to do with geospatial processing? That will be a subject for another post...

5 comments:

JC said...

Hey, Just wanted to say thanks.

I need to solve tis exact problem, and Google took me to you :)

Dr JTS said...

Excellent! It took me a while to track down and sort out all this info - so happy that it's helping out someone else.

Aditya Vikram said...

Thank you very much for this excellent reference.

Leonard said...

I had a similar problem to solve and this helped a lot, now I understand the problem completely. Thanks man.

Vineet George said...

I have found a method to find a unique and distinct number of the selected objects from the sample space. To have a look of this study then visit my site https://sites.google.com/site/junctionslpresentation/home

and also visit the site https://sites.google.com/site/junctionslpresentation/proof-for-advance-permutation

At the bottom of this site I have attached many Microsoft word documents. This documents mentions my study based on Junctions.