Factoradics as Permutation Odometers

I originally intended for this blog to cover more general scientific programming topics, but it has ended up being pretty much all cheminformatics. So I had been thinking about doing a more general post and when I came across this blog entry while searching google I knew I had found something to write about.

Enumerating permutations using inversion vectors and factoradic numbering

The author links to the Wikipedia entry for factoradic which gives this definition:

Factoradic is a factorial-based mixed radix numeral system: the i-th digit, counting from right, is to be multiplied by i!

radix:	7	6	5	4	3	2	1	0
place value:	7!	6!	5!	4!	3!	2!	1!	0!
in decimal:	5040	720	120	24	6	2	1	1

The first 6 factoradic numbers are:

	1100
	120100
	121100
	220100
	221100
	13020100

Wikipedia gives the subscript for readability but they are frequently written with commas dividing the place value as e.g., 2,1,0 which is more computer friendly. For more information you can also consult the entry in The Encyclopedia of Integer Sequences.

What's exciting about factoradics is that they provide a simple mapping between integers and permutations. The digits of the nth factoradic number can be used to obtain the nth permutation of a set of indices in lexicographical order.

I was intrigued by the idea of using factoradic numbers as permutation odometers. Lexical order is an odometer order if the set in question consists of numbers or letters. Since we're going to be working with indices, this holds true. For those not familiar with the concept, a permutation odometer is a means of controlling permutation generation that allows certain operations to be performed easily. These include: setting, reseting, rewinding, and fast-forwarding from a given permutation. You can read a basic introduction to base-n and base-10 odometers at this link.

In defining a type to represent a Factoradic we want something would act like an integral value type but readily supply the info necessary to obtain a permutation. I won't go into the details of how to get the permutation since they're given in the wikipedia entry and will be discussed in the follow up post. The important thing is that if I wanted to to, I could write some code like this

Factoradic fac = new Factoradic(11322);
while(fac < 0)
{
 fac -= 4;
 list.GetNthPerm(fac);
}

and generate every 4th permutation of a list in reverse lexicographical order starting with the 11,322 one. The operators ++, --, +=, etc. correspond to the operation odometer operations. Why would I want to do this? The reasons will be come abundantly clear later on. As a teaser take a look at the wikipedia entry on combinadics, which provide a similar mapping for the kth permutation of n items from a set.

Another important application of the factoradic is the generation of random permutations. Once we've defined the function GetNthPerm we can simply pass it a random integer. This has application in cryptography as well as software testing. The MSDN has an article which looks at this topic in depth.

This gist contains the source for my implementation of a Factoradic structure. Please bear in mind that it is a work in progress.

The maximum value that can be converted to/from an integral type is ulong.MaxValue while the maximum value that can be currently be stored is 20*20! Thats not bad, it gets us the approximately 10^19 permutations that can be generated by from naive implementation. I suspect that with some reordering of the list we could at least double that. We will also be able to use permutation patterns to our advantage, but that is definitely a topic for a later post.

Look for the next installment in a week or so. It will focus on the my implementation of the Factoradic structure and give some example code for actually generating the permutations.