From:

~~~ ~~~ Subject:

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.