4
$\begingroup$

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:

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you for the response, Peter, but maybe I'm missing the answer. Your answer looks like the difference between "pick" and "choose" (the number of k-size permutations of n items vs. the number of k-size combinations of n items). I wan't a unique index for each partial permutation. E.g. for (0 1 2 3 4 5) the index is 0; (0 1 2 3 4 6)->1; (0 1 2 3 4 7)->2; (10 2 3 6 4 9)->565731; (11 10 9 8 7 6)->665279. $\endgroup$
    – benbotto
    Apr 18, 2019 at 15:55
  • $\begingroup$ The lexicographic rank of [a, b, c, ...] is the total number of objects starting with something less than a plus the lexicographic rank of [b, c, ...] in the reduced problem where a has been deleted from the set of possibilities. That's just what the Lehmer code does, using $\binom{n}{k}$ to count the number of unordered subsets. $\endgroup$ Apr 18, 2019 at 16:06
  • $\begingroup$ I appreciate the answer, but I'm not following it. Would it be possible to provide a quick example? For example, mapping the partial permutation (10 2 3 6 4 9) to the index 565731? $\endgroup$
    – benbotto
    Apr 18, 2019 at 19:22
  • $\begingroup$ How about some working Python code? $\endgroup$ Apr 18, 2019 at 20:48
  • $\begingroup$ Man, I was so close! It's almost the same as the algorithm I use for the corners. Thank you kindly for the help, Peter. $\endgroup$
    – benbotto
    Apr 18, 2019 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.