Representation of edge permutations and move table

While I had a different solution to the problem of efficiently computing the effect of the basic cube moves on permutations of the edge cubies, I note that Herbert Kociemba's idea would involve fewer operations, and thus, could be significantly faster. So I've taken a close look at this scheme, particularly how to start with a usual cubie level representation, and transform it into a pair of coordinates as described by Herbert Kociemba.

First I used GAP to get a set of generators for M₁₂.

gap> M12 := MathieuGroup(12);
Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6),
  (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])

I implemented a C++ program that first did a God's algorithm calculation using the three generators GAP listed, and their inverses. (The last generator is its own inverse, since it has only two-cycles, so I used 5 elements of M₁₂ as the basic moves for this God's algorithm calculation.) The purpose of doing the God's algorithm calculation was to enumerate all 95040 elements of M₁₂. The distances were not important.

I then produced all products s₇*m₁₂ for s₇ in S₇ and m₁₂ in M₁₂, and verified that all 12! elements of S₁₂ were reached. Since there are exactly that many such products (95040*5040 = 479001600 = 12!), I had now shown that there was indeed such a unique decomposition for the set of elements in S₁₂.

I also observed that for each way 8, 9, 10, 11, and 12 could be permuted in S₁₂, there was one and only one element of M₁₂ that would permute them to their "solved" positions. Now, the perm_n_pack function I use converts permutations to a "mixed-radix" number. The five most-significant "digits" of the mixed-radix number represent how the first five "things" are permuted, not the last five things. For this reason (along with the fact that I like to use 0-based numbering in C++ code), I did a renumbering of the numbers used in the cycle notation given above for the generators of M₁₂. My generators were now:

(11,10,9,8,7,6,5,4,3,2,1,11)
(9,5,1,4)(8,2,7,6)
(0,11)(1,10)(2,5)(3,7)(4,8)(6,9)

The function perm_n_pack that I've talked about will take an array containing the integers 0 to n-1, and create a "mixed-radix" number. For n=12, the generated number is from 0 to 12!-1. But how 0 through 4 are permuted is represented by the 5 most-significant mixed radix digits. So if you divide the number by 7!, you get a number in the range 0 to 95040-1 that indicates how the numbers 0 through 4 are permuted. So each element of M₁₂ can be represented by an integer in the range 0 to 95040-1 by taking its "perm_n_pack number," and dividing by 7! (5040). A table of 95040 4-byte integers can be used to do the conversion in the reverse direction. Now, I will assume that the array from which the "perm_n_pack number" is generated has an element for each cubie, and the value of each array element gives the cubicle where it is located. (I like to call this "where-is" representation; while the converse I like to call "what's-at" representation, as that would have an array element for each cubicle, and the value giving what cubie is at that location.)

Now, assume g represents some element of S₁₂. Since the 0,1,2,3, and 4 can be permuted to their proper positions by some unique element m in M₁₂, we have g*m = s, and s must be some element of the isomorphism of S₇ that permutes 5,6,7,8,9,10, and 11. This can be rewritten as s * m^-1 = g. So it turns out that if x is the "perm_n_pack number" for g, then x/7! will be the index for m^-1. Since m is picked to be the element that permutes the cubies 0..4 into their proper cubicles, m will also permute the cubies 5..11 (for element g) into cubicles 5..11 (but generally not into the proper positions for each cubie). So I built a look-up table so that when given an M₁₂ element m, it returns a "perm_n_pack number" (n=7) representing how the inverse of m permutes the final seven cubies. I called this table M12S7table.

So "multiplying" the element of S₇ represented by x mod 7! by the element of S₇ represented by the number from the lookup table just mentioned, results in the desired element of S₇. Herbert Kociemba's post mentioned using a lookup table to for "multiplying" S₇ elements, and that same lookup table can be used here.

The routine for decomposing a position with "perm_n_pack number" s12 into a pair of indices for S₇ and M₁₂ elements thus looked like this:

typedef unsigned int UINT;

void
decomposeS12 (UINT s12, UINT* ps7, UINT* pm12)
{
	UINT hi = s12 / 5040;
	UINT lo = s12 % 5040;
	UINT m12s7 = M12S7table[hi];
	*ps7 = s7table[m12s7][lo];
	*pm12 = hi;
}

I note that the multiplication table for S₇ that I created was for "multiplying" numbers representing "what's at" values. As Jerry Bryan has commented before, such a table can be used for "multiplying" values for "where-is" representation by interchanging the subscripts. So for "where-is multiplication," I put the number representing the first "factor" as the 2nd subscript.

The routine for making a move, is then more or less as implied by Herbert Kociemba's post. I omit here the details of building the move table (here called M12_move_table).

void
apply_move (int move_code, UINT* ps7, UINT* pm12)
{
	UINT x = M12_move_table[*pm12][move_code];
	*ps7 = s7table[x % 5040][*ps7];
	*pm12 = x / 5040;
}

I verified my code by starting with a cube with all edges in place, and applying a randomly selected move sequence: U L^-1 B² R D F^-1 L² U^-1 R^-1 and converting the resulting (S₇,M₁₂) pair back to a cubie level representation, and got the expected result.

As you can probably guess, I needed to find some solution to this problem when I did the permutation of the cubies analysis. Instead of creating a move table based upon the edge permutation "coordinate" value, I instead converted the "coordinate" into a twelve-element cubie array, altered the four elements of that array that needed to be changed, and then converted the array back into a "coordinate" value. Since the actual move was just a matter of copying four of the array elements to different elements, that part is reasonably fast. The problem then was the time it took "perm_n_pack" and "perm_n_unpack" to execute.

To make move calculations faster, I felt it would probably be sufficient to come up with a faster versions of "perm_n_pack" and "perm_n_unpack" for the n=12 case. I called these routines "fast_ep_pack" and "fast_ep_unpack".

For fast_ep_pack, I first created two "base-12 numbers" from the first and 2nd halves of the 12-element array of edge cubicle contents. Then I calculated the edge permutation value using two lookup tables (called hi6_to_epermhi and lo6_to_epermlo) and the formula 720*hi6_to_epermhi[n₁] + lo6_to_epermlo[n₂] where n₁ is the "base-12 number" for the first half of the array, and n₂ is the "base-12 number" for 2nd half of the array. These lookup tables have a fair amount of "don't care" elements, but I was willing to trade off the space for speed. The lookup tables contained 2985984 elements each, or 11943936 bytes each.

For fast_ep_unpack, I used three lookup tables. I converted the number in the range 0..12!-1 to two 6-digit base-16 numbers. (I used base 16 instead of base 12 so I could use bit masking/shifting operations to extract the digits instead of division/modulo operations.) The "digits" were then transferred to the array elements. The code looked something like this:

	typedef unsigned int UINT;

	UINT eph = ep / 720;
	UINT epl = ep % 720;
	UINT eph6 = epermhi_to_ep_hi6[eph];
	UINT c6 = epermhi_to_combo_idx[eph];
	UINT epl6 = epermlo_to_ep_lo6[epl][c6];

The code to copy the "digits" from eph6 and epl6 to the output array are omitted here.

Note that to compute the values in the 2nd half of the array (last 6 cubicles), you need to know what set of 6 cubies were in the first 6 cubicles (but do not need to know what order). The epermhi_to_combo_idx lookup table maps the high order 6 mixed-radix digits of the edge permutation number into a number in the range of 0..(12 choose 6)-1 according to what set of 6 cubies are in the first 6 cubicles. So epermlo_to_ep_lo6 has 720*924=665280 elements, or 2661120 bytes. The other two lookup tables contain 12!/6! elements, or 2661120 bytes for one of them and 1330560 bytes for the other.