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 implementing and optimizing code. The examples are in C++, and will compile with g++ using the 2017 standard. I’m also going to reference the Rubik’s Cube a few times since it’s such a great illustration of permutation groups; you should know what a Rubik’s Cube is and how it moves.

A Brief Refresher on Permutations

A permutation is an arrangement of a set of numbers or objects. Unlike a combination, the order of a permutation is important, so (0 1 2) is different than (2 1 0). There are two types of permutations.

1. Permutations with replacement. For example, the PIN number of a debit card may have repeating digits.
2. Permutations without replacement, like a group of people in line. A line has an intrinsic order to it, and no person can be in line twice.

Indexing permutations with replacement is trivial, so I’ll only be covering the latter. From here on out, “permutation” refers to a permutation without replacement.

Given a set of n items, there are n! possible permutations of that set. So, for example, the set {0 1 2} can be permuted 3! = 3 * 2 * 1 = 6 ways. Those 6 permutations and their lexicographic ranks — the thing we’re after — are: 0: (0 1 2) ;1: (0 2 1) ; 2: (1 0 2) ; 3: (1 2 0) ; 4: (2 0 1) ; 5: (2 1 0) .

For a set of n items picked k ways, there are nPk (read “n pick k”) possible permutations. That’s calculated as n!/(n-k)!. As an example, given a set of 4 things, 2 of them can be picked 4!/(4–2)! = 24 / 2 = 12 ways: (0 1); (0 2); (0 3); (1 0); (1 2); (1 3); (2 0); (2 1); (2 3); (3 0); (3 1); (3 2). Those are ranked 0–11, respectively.

The Lehmer Code

Calculating sequential indexes for permutations is done by computing the Lehmer code of the permutation, and then converting that Lehmer code to a base-10 number. Before diving into that process, let’s take a minute to consider a base-10 number, say 3120. The number can be broken up into constituent parts: 3*10³ + 1*10² + 2*10¹ + 0*10⁰ = 3120. Like that base-10 number, a Lehmer code is just a sequence of digits; however, each digit has a different base. Technically, it’s a mixed-radix numeral system known as a factorial number system. Those same digits, 3, 1, 2, 0, have respective bases of 3!, 2!, 1!, and 0! in a factorial number system. That in mind, converting the Lehmer code 3120 to base 10 is simple: 3*3! + 1*2! + 2*1! + 0*0!.

Computing the Index of a Permutation in O(n²) Time

There’s a straight-forward quadratic algorithm on Wikipedia for calculating the Lehmer code of a permutation, but it’s rather inefficient for a computer since it involves splicing items out of an array. An equivalent algorithm that’s easy to compute is as follow. For each element of the permutation, the associated digit of that permutation’s Lehmer code is that element less the number of permutation elements to its left that are less than it (Korf, et. al.). I know that’s a bit rough to digest, so let’s go through a step-by-step example and calculate the Lehmer code for the permutation (2 0 1).

1. The first element of the permutation is 2. There are no elements to its left, so the first digit of the Lehmer code is 2.
2. The second element is 0. None of the elements to its left are less than it, so the second digit of the Lehmer code is 0.
3. And the last element is 1. It has one element to its left that is less than it, so the final digit of the Lehmer code is (1–1) 0.

(2 0 1) thus has a Lehmer code of 200. Converting that to base-10 (2*2! + 0*1! + 0*0!) yields 4. Indeed, (2 0 1) is the fourth (zero-indexed) permutation of the set {0 1 2} , lexicographically ordered.

It’s worth pointing out that this algorithm works provided the set of numbers in the permutation are zero-based. That is, it will work for the set {0 1 2}, but the set {5 6 7} would need to be translated.

Now, since English is hard to read and code is easy, here’s how that looks in C++.

For simplicity, the above will obviously only work with permutations of three numbers. Later on we’ll make the code generic.

A Few Quick Optimizations

One thing to note about Lehmer codes is that the right-most digit is always 0. In other words, no matter what element is last in a permutation, there will always be an equal number of elements to its left that are less than it. An obvious optimization then is to hard code the last element of lehmer to 0 and iterate from 1 to perm.size()-1 . This holds true for full permutations only, not partial permutations (discussed below).

Another easy optimization is to get rid of the recursive factorial function in favor of a precomputed array of factorials. Further, the last two calls to factorial are superfluous because 1! = 0! = 1.

Those minor changes aside, there’s not much more that can be done to speed this algorithm up. It’s quadratic in complexity, and that simply will not do. Solving a puzzle like the Rubik’s Cube involves computing permutations billions of times, and the above piece of code can (and in my case, did) outright dominate CPU time. We need a better algorithm.

A Linear Algorithm

If you’re familiar with the Rubik’s Cube or other permutation puzzles, then the name Richard Korf may sound familiar. Way back in 1997 he published the first optimal solution for the Rubk’s Cube (and it ran on a Sun SPARC Ultra!). It turns out that Korf also published a linear algorithm for encoding permutations (Large-Scale Parallel Breadth-First Search). The description is terse.

We scan the permutation from left to right, constructing a bit string of length n, indicating which elements of the permutation we’ve seen so far. Initially the string is all zeros. As each element of the permutation is encountered, we use it as an index into the bit string and set the corresponding bit to one. When we encounter element k in the permutation, to determine the number of elements less than k to its left, we need to know the number of ones in the first k bits of our bit string. We extract the first k bits by right shifting the string by n − k. This reduces the problem to: given a bit string, count the number of one bits in it.

We solve this problem in constant time by using the bit string as an index into a precomputed table, containing the number of ones in the binary representation of each index.

Let’s work through this algorithm by way of example, again using the permutation (2 0 1).

1. Start with a bitset of length 3, initialized to zero (000b).
2. The first element of the permutation is 2, so flip bit 2 of the bitset: 001b. As mentioned above, the first digit of the Lehmer code is always the same as the first digit of the permutation, 2 in this case.
3. The second element of the permutation is 0, so set bit 0 of the bitset: 101b. Right-shift the bitset by n - k, where n is 3, the number of elements in the permutation, and k is 0, the second element of the permutation. 101b >> (3-0) = 000b. Count the number of ones in the result (countOnes(000b) = 0), and subtract that from the element to get the Lehmer digit: 0 - 0 = 0.
4. The third element of the permutation is 1, so set bit 1 of the bitset: 111b. Right-shift: 111b >> (3-1) = 001b. Subtract the number of ones in the result from the element to get the Lehmer digit: 1 - countOnes(001b) = 1-1 = 0.

As expected, the Lehmer code is 200.

Above, the hypothetical countOnes function would just count the number of ones in the binary representation of a number, so calling the function with 1, 2, 3, 4, and 5 would return 1, 1, 2, 1, 2, respectively. Korf proposes implementing that in constant time using a precomputed table.

Here’s how the algorithm might look in C++. Note that the std::bitset class indexes bits from right to left, so the right-most bit is at index 0.

Again, the code will only work for permutations of three elements, but a generic version of the function is given at the end of the article.

Indexing Partial Permutations

Creating an index for a partial permutation is pretty much the same: calculate a Lehmer code for the permutation, then convert it to a base-10 number. But the last part — converting to base-10 — is slightly different. For a full permutation, each digit in the Lehmer code has a base of (n-1-i)!, where n is the number of digits in the Lehmer code and i is the index of a digit. For a partial permutation, the base of each digit is (n-1-i)P(k-1-i), where k is the number of items picked from the set of n items.

Let’s say we have a set of 4 items picked 2 ways. The (arbitrary) partial permutation (1 3) has a Lehmer code of 12. Converting that to base-10:

1 * (4-1-0)P(2-1-0) + 2 * (4-1-1)P(2-1-1) = 1 * 3P1 + 2 * 2P0 = 5.

A Generic Method for Indexing Permutations

Putting everything together, here’s a generic PermutationIndexer class that can compute sequential indexes of both partial and full permutations. Example usage is show at the bottom in the main method.

The generic version is largely the same, but updated slightly to accommodate partial permutations. Drop me a comment if you have any questions.

Need a Developer?

Get in touch! We’re a small software company in Folsom, California, and we would love to help you out.

References

• Botto, Ben. rubiks-cube-cracker.
• Korf, Richard et. al. Large-Scale Parallel Breadth-First Search
• Wikipedia. Factorial number system.