Calculating Symmetry using Representative Elements
I have long been curious how other people who write cube programs and who incorporate symmetry into their programs actually do the symmetry calculations. The general way I do it has been outlined in Cube-Lovers.
For a given position x, I calculate a representative element of its m-conjugates, where M is the standard Cube-Lovers terminology for the 48 symmetries of the cube. I then store and manipulate only the representatives.
We denote this calculation as y = Rep(x) = min{x^{M}} = min{x^{m} | m in M}. The minimum element of x^{M} is taken to be the one that is first in lexicographic order. And as usual, x^{m} means m^{-1}xm, and x^{M} means {x^{m} | m in M}.
The calculation seems simple enough. You calculate in turn
(m_{0})^{-1}xm_{0},
(m_{1})^{-1}xm_{1},
....
(m_{47})^{-1}xm_{47}
and keep the smallest conjugate as the representative.
But it's not a very fast calculations. There are lot of loops
within loops within loops. Here are some things I have done
through the years to make the calculations faster.
Suppose we are comparing two strings such as "cat" and "dog". Any program would compare the "c" to the "d" and then stop. It's only necessary to compare additional characters to break ties, as in comparing "cat" to "car". In the later case, the tie would not be broken until you reached the third character of each string.
The situation with comparing x to m^{m} is slightly different than the situation with comparing "cat" to "dog" Presumably, in the case of "cat" and "dog", both strings already exist. But in the case of x and m^{m}, x presumably already exists but m^{m} doesn't. Rather, m^{m} has to be calculated.
It's as if you were comparing the string "cat" to the unknown string "???" that first has to be calculated. You could calculate the entire unknown string "???" as "dog", and then compare "cat" to "dog". Or, you could calculate the unknown string one character at time and compare after each character. So you could calculate the first character of "???" yielding "d??", then compare the "c" to the "d" and you are done. But if you calculate the first character of "???" yielding "c??", then you have to go on and calculate the next character yielding "ca?" and so forth. In any case, you calculate and compare in the same loop, you stop the loop after the first unequal compare, and there are usually many fewer characters to calculate that way.
Similarly, I don't calculate the entire permutation x^{m} and then compare it to the permutation x. Rather, I calculate each unitary partial permutation of x^{m} in turn, and compare each unitary partial permutation of x^{m} to the corresponding unitary partial permutation of x.
Here's an example. The basic model for the cube in my programs
is S_{24} x S_{24}, with S_{24} acting on
0...23 rather than on 1...24. A position for the corners might look
something like
x=(9 2 5 0 22 3 7 4 17 10 13 8 6 11 15 12 1 18 21 16 14 19 23 20)
For some fixed m, we might calculate the first unitary partial permutation as
x^{m}=(15 * * * * * * * * * * * * * * * * * * * * * * *)
Therefore, because 15 is greater than 9, we
know that our particular choice of m does not yield a representative element
for the permutation x without calculating the rest of the
permutation x^{m}, and we go on to the next m.
Before proceeding further, I will point out that with an S_{24} model for the corners or for the edges, it's not necessary to store all 24 unitary partial permutations. It's only necessary to store 8 of them for the corners, corresponding to one facelet per corner cubie. And it's only necessary to store 12 of them for the edges, corresponding to one facelet per edge cubie. That's why I think most programs model the cube with a wreath product representation for the corners and for the edges, rather than an S_{24} representation for the corners and for the edges. But some of what I'm about the explain is easier if I temporarily maintain the fiction that I'm storing all 24 unitary partial permutations, both for the corners and for the edges.
Based on what I have described so far, the basic scheme for finding Rep(x) is to take x itself as a first approximation for the representative. There is then a loop that goes through all 48 values for m, calculating and comparing x^{m} one unitary partial permutation at a time to the current approximation for the representative. Any time the current x^{m} is smaller than the current approximation, it becomes the new approximation. A very minor enhancement is that I make sure that m_{0} is the identity element of M, and then the loops only have to run from 1 to 47 rather than from 0 to 47.
The procedure I have described is not too bad. Most values of x^{m} can be discarded after the calculation of only one unitary partial permutation. But there is still a performance problem. As you loop through the 48 values for m, there will usually be several times where you do encounter a value for m that yields a value for x^{m} that is smaller than the current best approximation for the representative. So the value of x^{m} becomes a new current approximation. The new current approximation for the representative has to be calculated in its entirety, even though it may not become the final representative.
We can address this performance problem as follows. We have a loop that for each value of m calculates only its first unitary partial permutation. As we go through the loop, we maintain a list of m values that minimize the first unitary partial permutation. And it is only those values of m that possibly can yield the representative for x. Such a list of m values usually only contains two or three values for m, and it is then only those two or three values that have to be used to calculate x^{m}, rather than all 48 values of m.
Of course, the list of m values is quite dynamic as it is being built. The list starts out consisting only of m_{0}. Let's say that m_{0} yields a first unitary partial permutation of (9 * * ....). If m_{1} yields (12 * * ....) we don't add m_{1} to the list. If If m_{2} yields (9 * * ....) we add m_{2} to the list, and the list now consists of m_{0} and m_{2}. If m_{3} yields (7 * * ....), we start the list over again, containing just m_{3}. Etc.
This new approach is much faster, but it still requires looping through all 48 values of m, even if just to calculate just one unitary partial permutation for each m. It's possible to do a little better still.
Normally, we calculate m^{-1}xm left to right in the obvious fashion. For example, suppose we want to calculate m^{-1}xm: 0 -> k, which we have been denoting as m^{-1}xm = (k * * * ...). We would send 0 through m^{-1}, yielding i. We would send i through x yielding j. And we would send j through m yielding k. But it's also possible do the calculation "from the middle", as it were.
Let's go back to our example for the corners of a position where
x=(9 2 5 0 22 3 7 4 17 10 13 8 6 11 15 12 1 18 21 16 14 19 23 20)
The first unitary partial permutation is 0->9. There are
exactly two elements of M for which m^{-1} maps 0->9.
The way my tables are set up, they are m_{0} and m_{35}.
m_{0} is a rotation and m_{35} is a reflection.
Conjugation by m_{0} yields (0->0)(0->9)(9->9)=9.
Conjugation by m_{35} yields (0->0)(0->9)(9->19)=19. So
conjugation by m_{0} might minimize x^{m}, but conjugation
by m_{35} cannot.
The second unitary partial permutation is 1->2. There are exactly two elements of M for which m^{-1} maps 0->1. The way my tables are set up, they are m_{3} and m_{34}. m_{3} is a rotation and m_{34} is a reflection. Conjugation by m_{3} yields (0->1)(1->2)(2->1)=1. Conjugation by m_{35} yields (0->1)(1->2)(2->1)=1. So conjugation by m_{3} might minimize x^{m}, and conjugation by m_{34} might also minimize x^{m}. But we have now eliminated m_{0} as a possibility.
We can continue in this vein through the last unitary partial permutation, which is 23->20. For each i->j, there will be exactly two possible values of m for which m^{-1} maps 0->i. One of the m values will be a rotation, and the other m value will be a reflection. By the time we have examined each of the 24 unitary partial permuations in this manner, we will have considered each of the 48 possible values for m as a candidate for minimizing x^{m}.
On it's face, it may not seem that we have made much progress. We have reduced 48 loops down to 24 loops to try to find our list of initial m values that might minimize x^{m}. But remember that we really only store 8 of the unitary partial permutations, not all 24 of them, were are unitary partial permutation corresponds to a single facelet of the cube.
For example, instead of storing
x=(9 2 5 0 22 3 7 4 17 10 13 8 6 11 15 12 1 18 21 16 14 19 23 20)
we really only store
x=(9 2 5 0 22 3 7 4)
For facelet number 9, we know that it is connected to facelet number 17
and to facelet number 1 to form a complete cubie. So for example,
we can take,
x=(9 * * * * * * *)
and determine that it really means
x=(9 * * * * * * * 17 * * * * * * * 1 * * * * * * *)
That is, facelet 9, facelet 17, and facelet 1 are a part of a single cubie that we might call the (9,17,1) cubie. It turns out that the way I number the facelets, the (9,17,1) cubie is the urf cubie in Singmaster notation. For our purposes here, that means that we know that if see the unitary partial permutation 0->9, we are also going to have the unitary partial permutations 8->17 and 16->1. So instead of 2 possible m values we have identified to look at, we have 6 possible m values, namely the two for 0->9, the two for 8->17, and the two for 16->1. Our loop only has to go 8 times instead of 24, and each loop can consider 6 possible m values.
Essentially all of this information can be placed in tables during
program initialization. For example, the following might be the case
for
x=(9 2 5 0 22 3 7 4)
- 0->9 m_{0} yields 0->9
- 1->2 m_{34} and m_{3} yield 0->1
- 2->5 m_{19} yields 0->12
- 3->0 m_{17} and m_{35} yields 0->4
- 4->22 m_{5} m_{16} and m_{29} yield 0->6
- 5->3 m_{23} yields 0->5
- 6->7 m_{29} yields 0->11
- 7->4 m_{28} yields 0->1
So clearly, the best we can do is 0->1, and the only values for m that we need to consider are m_{34} m_{3} and m_{28}. The loop only had to run 8 times, and it quickly reduced the number of possible m values from 48 down to only 3. Most of the m values are actually eliminated during the building of the lookup tables during program initialization. For example, during its consideration of 7->4, the initialization code did actually consider six different possibilities for m. But only one of the six, namely m_{28}, mapped 7->4 to 0->1. The other five mapped 7->4 to 0->k where k was greater than 1.