Here is a rough sketch of Shamir's algorithm, as he presented it at the
talk last Friday. The fact that I have typed this in does not
-necessarily- indicate a willingness on my part to supply any further
details. Nor do I guarantee that my description will enable you to
correctly reconstruct the algorithm, although I tried to make it
comprehensible.

I think Shamir gave credits for a couple of graduate students of his for
some of this, but I didn't make a note of their names. It is always nice
to give people proper credit...

You are given a scrambling of the cube, and you want to know if the cube
can be restored in 4*N quarter twists. (Shamir is a half-twister, but I in
this message I will rephrase everything in quarter-twist terms. It makes
little difference, the algorithm applies equally well to any set of
generators.)

Represent a permutation as a vector that simply lists the values of the
permutation. That is, if the permutation sends 0 to 7, 1 to 2, 2 to 4, 3
to 1, etc., then the vector [7, 2, 4, 1, ...] represents it.

We will be ordering permutations in "dictionary order". That is, a
permutation sigma is less than a permutation tau just in case there exists
an i such that

sigma(i) < tau(i) and for all j < i, sigma(j) = tau(j).

We start by generating a list of all permutations generated by N quarter
twists. The algorithm requires space to store several datastructures
proportional to the size of this list. (If N=5, this list has 93840
elements. Its size is about 10^N for the cube group in quarter twists.
For an arbitrary group and generators it will be exponential in N.)

Now what we would like to do is generate -and- -sort- the list of all
permutations generated by 2*N quarter twists. We could do this by simply
multiplying all possible pairs of elements from our list, and then sorting
again, but this generates an absurdly large list, that it takes an absurd
amount of effort to sort.

The trick is to generate this list of products both incrementally and
already sorted! This gives us the ability to ask for the -next- element of
the list, which is exactly what we need: Given two such permutation-list
generators we can easily scan through both lists to see if any element
occurs in both lists (using an algorithm that the reader can easily
reconstruct). Thus we can build one generator for the list of all
positions 2*N twists away from solved, and another for positions 2*N twists
away from the given one, and if we find an element on both lists, then we
have a 4*N twist solution.

OK, so how do we construct this magic generator?

First we take the list of length N permutations and make it into a tree.
There will be one leaf for each permutation in the list. All permutations
that share a common prefix will share a common internal node in the tree.
For example, given the permutations:

[0, 1, 2, 3, 4]
[0, 1, 3, 2, 4]
[1, 0, 3, 4, 2]
[1, 3, 0, 4, 2]
[2, 3, 1, 4, 0]

we get the tree:

                      [0, 1, 2, 3, 4]
                     /
                    /2
         [0]--[0, 1]
        /   1       \3
       /             \
      /               [0, 1, 3, 2, 4]
     /
    /0        [1, 0, 3, 4, 2]
   /         /
  /         /0
[]-------[1]
  \  1      \3
   \         \
    \2        [1, 3, 0, 4, 2]
     \
      \
       \
        \
         [2, 3, 1, 4, 0]

Now consider one element of the original list, say

sigma = [2, 3, 1, 4, 0].

We want to find the permutation tau, such that sigma * tau is smallest in
dictionary order. So, what is the first entry of sigma * tau? That is,
what is sigma(tau(0))? Well, looking at sigma we can see that -if-
tau(0) = 4, then sigma(tau(0)) = 0. Unfortunately their are no
permutations in our list that start with 4, but we can get
sigma(tau(0)) = 1 if tau(0) = 2. Now there is only one such permutation on
our list, so that must be it:

tau = [2, 3, 1, 4, 0] (= sigma as it happens).

What about the tau such that sigma * tau is -second- smallest? We have
exhausted permutations with tau(0) = 2, what should we consider next? Well,
if tau(0) = 0, then sigma(tau(0)) = 2, so we should next consider
permutations that start with 0. After that, we should do those that start
with 1, followed by those that start with 3.

The exact same argument applies to tau(1). That is, to minimize the
product, first consider permutations such that tau(1) = 4, followed by
tau(1) = 2, then tau(1) = 0, then tau(1) = 1, and finally tau(1) = 3.

Thus you can see that to generate the sigma * tau products in order, we can
just take tau to be successive leaf nodes in the above tree, where we order
the inferiors of any internal node in the order 4, 2, 0, 1, 3. It is easy
to generate this ordering given sigma.

Now for -each- permutation sigma in our original list we will be taking a
different walk through the tree using a different ordering of inferiors.
So we maintain a queue of pairs <sigma, tau>, sorted according to
sigma * tau. When called upon to generate the next element of the
list-of-products, we take the head of the queue (smallest) and return it.
Then we advance to the next tau for the given sigma, and insert the new
pair <sigma, tau'> back into the queue.

Modifying this construction to generate permutations of the scrambled
position, rather than solved is easily accomplished by first composing the
inverse of the scrambling permutation with each element of the list of
length N permutations. Now we combine each element of this list with each
element of the same tree as above.

Analysis of space and time requirements left to the reader.