_{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...