Sequentially Indexing Permutations: A Linear Algorithm for Computing Lexicographic Rank

= 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 AlgorithmIf 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 useit 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 bitstring.

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).

Start with a bitset of length 3, initialized to zero (000b).

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.

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.

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 PermutationsCreating 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 PermutationsPutting 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.

ReferencesBotto, Ben.

rubiks-cube-cracker.

Korf, Richard et.

al.

Large-Scale Parallel Breadth-First SearchWikipedia.

Factorial number system.

.

. More details

Leave a Reply