Indexing Edge Permutations for the Rubik's Cube

Question

I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. His method involves creating three pattern databases: one for the 8 corner cubies; one for 6 of the 12 edge cubies; one for the remaining 6 edges.

My question is about indexing the permutations of the edge pieces. Mind you, each edge can be oriented in one of two ways, but my questions is not about the orientations, only the permutations.

With 6 edge positions and 12 edge cubies that could occupy them, there are 665,280 possible permutations (12 pick 6, or 12! / 6!). For simplicity sake, let's say the edge cubies are numbered 0-11. The 6-element partial permutations of these 12 cubies in lexicographical order is thus (0 1 2 3 4 5), (0 1 2 3 4 6), (0 1 2 3 4 7), ... (11 10 9 8 7 6). Is there an efficient way to index those permutations? Sequential indexing would be preferred, although that may not be possible.

One thought I had is to simply iterate through all 665,280 permutations and store the associated index. That's doable, although it's rather memory intensive. I'm looking for more of a minimal perfect hash approach.

For example, I have the indexing for the 8 corner cubies figured out. For the 8 corner cubies, the Lehmer code for each permutation can be computed, and then that Lehmer code can be converted to a sequential index. Korf describes how to do this in his 2005 paper, Large-Scale Parallel Breadth-First Search. However, that paper does not address indexing partial permutations.

Related questions:

• Indexing into a pattern database - Korf's Optimal Rubik's Cube solution
• https://math.stackexchange.com/questions/97813/a-positional-number-system-for-enumerating-fixed-size-subsets

Answer 1

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

In Python:

from functools import reduce
from operator import mul


def falling_factorial(n, k):
    return reduce(mul, range(n-k+1, n+1), 1)


def lexicographic_rank(n, perm):
    if len(perm) == 0:
        return 0

    a = perm[0]
    return a * falling_factorial(n - 1, len(perm) - 1) + \
        lexicographic_rank(n - 1, [i if i < a else i - 1 for i in perm[1:]])

Online demo