Sequentially Indexing Permutations: A Linear Algorithm for Computing Lexicographic Rank
Recently I wrote an optimal solver for the Rubik’s Cube that can solve any scrambled cube in 20 moves or fewer. Check it out if you’re interested. Anyway, solving the puzzle programmatically involves creating pattern databases that hold hundreds of millions of values, namely the number of twists required to solve subsets of the cube, like the number of twists necessary to solve the eight corners. Because such large datasets can easily exhaust system resources, the values in the databases are stored sequentially in plain arrays. Indexing into those databases means calculating sequential indexes for permutations, essentially generating a minimal perfect hash for a set of pieces of the puzzle.
In this article I’ll go over some algorithms for calculating sequential indexes for permutations, also known as the lexicographic rank for you math nerds out there. In a nutshell, the algorithm takes a permutation of a set of things and converts it into an integer. I’ll start with a simple algorithm that’s quadratic in complexity, and then present an equivalent linear version. Lastly, I’ll touch on indexing partial permutations.
This piece is intended for programmers. There are plenty of resources that describe in detail the math behind ranking permutations, but this writing focuses on…