In January of 1994, I wrote a small package for describing elements of a
permutation group in terms of its generators. There were some inefficiencies,
and the results were far from optimal, but it gives reasonable results, and
reasonably quickly. For example, for Rubik's Cube, it takes less than a minute
to "familiarize itself" with the cube. After this, I chose a random element
of the group, and ask for the solution. The calculations took .017 seconds.
The solution involved about 1200 moves. The worst case has about 1575 moves.
Much better than the 500,000 mentioned, but far short of optimal. I used
another routine to find a shorter version of the solution. This gives a
further reduced word, but it is still not optimal. In my last run, 85 seconds
of "Shrinking" gave a word of length 135. Of course, the timing results are
machine dependent. I am using a Sun workstation.
I placed the package in /pub/incoming at
email@example.com with the non-obvious name of AbStab. (This
is for "Abstract Stabilizer Chains.")
I haven't heard comments about it, and was curious as to if anyone has
used it, or if it has been moved to another location.
University of Minnesota