Representation of edge permutations and move table

Stimulated by the last thread, where the representations of permutations and orientations was dealt I want to ask, what would be a good representation for the 12! edge permutations on the coordinate level, if the right multiplication of the edge permutation by any of the generators U,L.... should also be done with a MoveTable on the coordinate level like newcoordinate = MoveTable[oldcoodinate][generator].

This MoveTable would have 12!*18 4 Byte entries when we take the coordinate from 0..12!-1 and of course is far too big. Of course we could reduce this by 48 symmetries, but then we still would have a very large table.

I never really needed to do this multiplication, but if found an approach, which I think is quite interesting.

The permutation group S12 can be written as the product of the permutation group S7 and the Mathieu group M12 of order 95040:
S12 = S7*M12, where the representation is unique for any element of S12.

So any element of S12 can be represented by a coordinate pair (a,b), where a is in 0..5039 and b in 0..95039.

Doing a multiplication with a generator then would work as following:

for example s12*U = (s7*m12)*U = s7*(m12*U) = s7*(s7'*m12') = (s7*s7')*m12'.

So the pair (a,b) is transformed to another pair (a',b'). To do the multiplication we need two tables. A table with 95040*18 entries gives the representation for the result of the multiplication of an element of M12 with a generator and a table with 5040^2 entries which gives the multiplication of two elements of S7.
I do not see a way to reduce these coordinate pairs by symmetry though, because M12 is probably not invariant under the conjugation with the cube symmetries.

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

I found out using GAP that if

I found out using GAP that if one conjugates M12 by an appropriate element x in S12 then the conjugate group x^(-1)M12x has 12 symmetries and hence one can write S_12=S7 x^(-1)M12x. I also proved there exists no x in S12 such that x^{-1}M12x has more than 12 symmetries.

EP sym-coordinate typically unnecessary

For my permutation of the cubies analysis, I used a corner permutation sym-coordinate for an approx. 40.98 reduction factor. For my edges-only (wrt fixed centers) analysis, I used an edge orientation sym-coordinate for an approx. 26.95 reduction factor. (Of course, I used an edge orientation convention that allows using the full cube symmetry group.) In both cases, I obviously got much better than a 12x reduction. So while it may be interesting to know that the (s7,m12) pair can be reduced using a sym-coordinate, there may be other better options for symmetry reduction for specific problems. If you're considering only edge permutation, I guess that is one case where you would benefit from this symmetry reduction. But you would generally like to have close to a 48x reduction if you can achieve this without really big lookup tables.

I do not understand your argu

I do not understand your argumentation.
1. With symmetries you mean some of the 48 symmetries of the cube?
2. Of course x^-1M12x is a group. But why it should be possible to write S_12=S7 x^(-1)M12x ?

Yes I mean the 48 symmetries

Yes I mean the 48 symmetries of the cube.

You said that S_12= S_7 M_12 in your previous post.

If you conjugate
S_12=x^(-1) S_12 x = x^(-1) S_7 M_12 x= x^(-1) S_7 x x^(-1)M_12 x

Replace x^-1 S_7 x= S'_7(a group isomorphic to S_7) then
S_12=S'_7 x^(-1)M_12 x

And x can be choosen in such a way that x^(-1)M_12 x is invariant under 12 symmetries of the cube.

Ok, if you say it is a group

Ok, if you say it is a group *isomorphic* to S_7 I agree. Is the symmetry group under which x^(-1)M_12 x is invariant the pointgroup T or D3d (Schoenflies notation)?

I am not sure which but I can

I am not sure which but I can tell you how I concluded this thing.

First I took a representation of S12,M,M_12 in GAP. Then I computed representatives of the coset space S12\M_12. This is done with the command RightTransversal. Then i took each representative x and computed the symmetries under which x^(-1)M_12 x is invariant. This is sufficient because any element y of S_12 may be written as mx where m is in M_12 an d x is a representative and (mx)^-1 M_12 mx = x^(-1)M_12 x. Because I represent M in terms of GAP generators it is difficult to find out to which group it corresponds. But I hope you can reproduce the calculation from this data. The computation took in GAP a couple of minutes. If you are interested I can send you the program.

I will try to fix this problem and give you the generators in terms of rotations and mirror reflexions.

Implementing Herbert's idea

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

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 M12 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 M12. The distances were not important.

I then produced all products s7*m12 for s7 in S7 and m12 in M12, and verified that all 12! elements of S12 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 S12.

I also observed that for each way 8, 9, 10, 11, and 12 could be permuted in S12, there was one and only one element of M12 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 M12. My generators were now:


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 M12 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 S12. Since the 0,1,2,3, and 4 can be permuted to their proper positions by some unique element m in M12, we have g*m = s, and s must be some element of the isomorphism of S7 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 M12 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 S7 represented by x mod 7! by the element of S7 represented by the number from the lookup table just mentioned, results in the desired element of S7. Herbert Kociemba's post mentioned using a lookup table to for "multiplying" S7 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 S7 and M12 elements thus looked like this:

typedef unsigned int UINT;

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

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 B2 R D F-1 L2 U-1 R-1 and converting the resulting (S7,M12) pair back to a cubie level representation, and got the expected result.

Was it worth the effort to im

Was it worth the effort to implement this code? How much better is the overall perfomance of your program now?

performance for edge permutation only - FTM

> How much better is the overall perfomance of your program now?

Were you expecting me to rerun my permutation of the cubies analysis? :-)

Well, so far I had basically implemented this to prove out the concept. It could have been useful in my permutation of the cubies analysis, or when I did the edges-only (wrt fixed centers) analysis (verifying Rokicki's QTM analysis). I actually implemented this by adding code to one of my older, existing programs that started out as a program for doing an analysis for edge permutation only. Following that, I added several other miscellaneous analyses to the program. Thinking that this analysis is about the right size to get you some comparative performance numbers, and the work to update the program would be rather minimal, I went ahead and did that. I did not want to take too much time away from the huge God's algorithm calculation I am currently working on.

So I ran the edge permutation only analysis (face-turn metric) using three different ways of handling calculating the moves:
(1) with my original code (using perm_n_unpack/perm_n_pack to convert to/from a cubie model),
(2) with fast_ep_unpack/fast_ep_pack to convert to a cubie model, and (3) with the S7/M12-based approach.
I also tried (3a) a variation of the third approach where I combined the S7 and M12 values into a single number, but this reduced performance slightly. I got the following results.

(1): 1 h 31 m  6 s
(2):     27 m 36 s
(3):     14 m 18 s
(3a):    17 m 39 s

By the way, the table of positions at each distance looks like:

distance  positions
   0              1
   1             18
   2            243
   3          3,240
   4         42,535
   5        542,234
   6      6,529,891
   7     66,478,628
   8    310,957,078
   9     94,443,600
  10          4,132
total   479,001,600

I am sure others must have done this analysis before, but I don't seem to find it on the internet.


Nice to see that the new approach doubles the speed.

I took a different approach

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[n1] + lo6_to_epermlo[n2] where n1 is the "base-12 number" for the first half of the array, and n2 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.