_{n}(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 S
_{n}(in lexicographic order) - Find the i'th permutation in S
_{n}

_{n}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 S

_{n, }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 = (p

_{1}p

_{2}... p

_{n}) where p

_{i}is in {1, 2, ..., n}

An inversion is a pair (p

_{i}, p

_{j}) where i < j but p

_{i}> p

_{j}. We define d

_{i}to be the number of inversions in the sequence where the first element is p

_{i}:

d

_{i}= | { p

_{j}: i < j , p

_{i}> p

_{j}} |

Then the inversion vector for the permutation is the sequence

D = (d

_{1}, d

_{2}, ..., d

_{n}) (d

_{i}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 S

_{n}, and their natural order gives a lexicographic ordering of S

_{n}. 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 d

_{i}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 S

_{8}.

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:

Hey, Just wanted to say thanks.

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

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

Thank you very much for this excellent reference.

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

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.

Post a Comment