Armed with some newfound understanding of Shamir's method,
I would like to revisit the issue of large searches in
small memory. However, I will be proposing the
application of Shamir's method in a slightly different
form than it has been applied before.

The best discussion of Shamir's method in the archives is
probably Alan Bawden's note of 27 May 87 "Shamir's talk
really was about how to solve the cube!". The thrust of
Shamir's talk was how to determine the minimal solution
for a given position in a reasonable time and with a
modest (relatively speaking!) amount of memory.

My take on the Shamir's method is two-fold. First, let
T[n] be the set of positions no greater than n moves from
Start, and let x be the position in question. Shamir's
method first involves taking the intersection of T[n] with
xT[n]. If the intersection is null, then x is greater
than 2n moves from Start. Otherwise, the distance from
Start can be determined rather easily. This is our old
friend which I call the half-depth search.

The efficacy of a half-depth search is dependent on n. A
reasonable n of say 5 or 6 only permits testing x up to a
distance of about 10 or 12 moves from Start.

The second component of Shamir's method is the clever
part. You store T[n] and create sort of a virtual T[2n]
which doesn't have to be stored. You do the same thing
with xT[n] to create a virtual xT[2n]. Forming the
intersection of T[2n] with xT[2n] lets you test positions
up to a distance of 4n from Start while only storing T[n]
and xT[n]. So for n=5, we can test for distances up to 20
moves from Start.

My primary interest lies in creating T[n] for the largest
possible n, rather than testing for particular positions.
Hence, I want to talk about just the portion of Shamir's
method that lets us get from a real T[n] to a virtual
T[2n].

Let me start be reviewing my understanding of key points
of Shamir's method. Given two sets of positions S and T,
Shamir tells us how to form all the products st for s in S
and t in T with the products being created in
lexicographic order. The storage required is order N
rather than order N^2 (provided of course that the
products are only created and are not stored).

For the algorithm to work, T itself has to be in
lexicographic order. I don't think S has to be in
lexicographic order (see below). But S and T may well be
the same set, and in any case there is no loss of
generality in requiring that S be in lexicographic order
as well.

Furthermore, T must be stored as a tree, and we might just
as well store S as a tree, too.

Alan gives an excellent description of the required tree
structure. The structure itself is a very old concept and
is not unique to Shamir's method. It could be used, for
example, to store a dictionary for a spell-checker. Such
a tree would branch 26 ways (American alphabet) for each
of the 26 possible first letters. The tree would branch
again in up to 26 ways for the second letter and for each
subsequent letter, etc.

For Shamir's tree, the "letters" are (usually one byte)
numbers defining the permutations, where the permutation
is simply a vector listing (in order) the values of the
permutation.

Choose a particular s[j] in S and consider all the
products (s[j])(t[k]) for t[k] in T and for k in 1..n.
There is some ordering of the t[k] values which will put
the {s[j])(t[k]) values in proper lexicographic order.
The t[k] values themselves are obviously not in
lexicographic order, and may indeed appear to be in a
"random" order. But the order is far from random; it is
quite carefully considered. The genius of Shamir's method
is that it tells us exactly how to accomplish the proper
ordering of the t[k] values to yield lexicographic
ordering of the {s[j])(t[k]) values.

Notice that the required order of the t[k] values is
different for each s[j]. My brief description of the
magic is that (s[j])' is used as a template to tell us how
to traverse the T tree to make the t[k] values come out in
the required order to make the (s[j])(t[k]) values come
out in lexicographic order. See Alan's note for
additional details.

(Alan doesn't mention (s[j])' explicitly, but that is what
it comes down to. Shamir reverse engineers s[j], runs it
backwards if you will, to figure out how to make
(s[j])(t[k]) come out right.)

The rest of the algorithm is a little fuzzy to me, but
here is how I think it has to work. Suppose S contains m
elements and T contains n elements. What we have done so
far is to create a single sequence of products
(s[j])(t[k]) for some particular, fixed s[j]. The
sequence contains n elements (one for each t in T), and is
in lexicographic order.

We must produce m such sequences, one for each s[j].
Then, we must perform an m-way merge of the m sequences.
The result of our merge is the desired sequence of
products st in lexicographic order. It is the fact of
this merge that leads me to believe that the s values do
not have to be in lexicographic (or any other particular)
order.

If m is very large (more than a few dozen), such a merge
is not quite so easy as it sounds, and it is the details
of the merge that are most fuzzy to me in Alan's note.
The merge would normally be accomplished by forming an
ordered queue containing the first element of each
sequence. The first element would be popped off the
queue, then the next element from that sequence would be
calculated and put into the queue.

The tricky part is that the queue has to be kept ordered.
It has to be ordered in the first place. Then, when an
element is popped off and a new element added, the new
element has to be added in the correct place. Hence, I
would probably implement the queue itself as another tree,
separate from the S and T trees.

Now, we return to our main discussion. Let Q[k] be the
set of positions which are k quarter turns from Start. (I
used C[k] in my last note). Q[1] is just Q, the set of 12
quarter turns. Store each Q[k] for k in 0..n in its own
"Shamir tree".

Create a virtual Q[n+1] as the lexicographically ordered
set of products st for s in Q[n] and t in Q[1]. Shamir
does not do everything for us. We have to do some of the
work ourselves at this point.

The first issue is that some of the products will be
duplicate. But the lexicographical ordering makes the
duplicates easy to detect. So detect the duplicates and
throw them away.

The second issue is that some of the products are in
Q[n-1] rather than in Q[n+1]. But since Q[n-1] is also in
lexicographical order, we can keep a finger or toe pointed
to Q[n-1], scanning through it in step with the products
which are generated. Any product which is found in Q[n-1]
is not counted as being in Q[n+1].

Creating virtual Q[n+2] is like unto creating virtual
Q[n+1]. We form products from Q[n] and Q[2]. An
additional complication is that our fingers and toes must
point to and step along both Q[n] and Q[n-2] looking for
products which are shorter than n+2 quarter turns, and
which therefore are not to be counted.

Now comes the really interesting part --- creating
virtual Q[n+3]. We form the products from Q[n] and Q[3].
As we create the products, we must track along through the
Shamir trees for Q[n-3], Q[n-1], and Q[n+1]. But the
Shamir tree for Q[n+1] is virtual, and isn't really there!

Here is how we do it. We must create virtual Q[n+1] and
virtual Q[n+3] at the same time, keeping them more or less
in step, with Q[n+1] equal to or one step ahead of Q[n+3].
That way, we have the one real element available of the
virtual Q[n+1] that we need to test the virtual Q[n+3]
against. As a really *old* programmer, I would describe
what we are doing with Q[n+1] and Q[n+3] as a match/merge.

Given the requirement to generate Q[n+1] as we generate
Q[n+3], there is no real reason to generate Q[n+1] by
itself. If we have enough fingers and toes to point to
and count everything, we might just as well produce Q[n+1]
and Q[n+3] on the same pass of the data. For that matter,
we might just as well get Q[n+1], Q[n+3], through Q[2n-1]
on the same pass. Similarly, we might as well get Q[n+2],
Q[n+4], through Q[2n] on the same pass.

This is all very simple in principle. But in my
experience, keeping track of all those pointers and
counters is a real pain to program.

Can we go again? That is, can we go from Q[2n] to Q[4n]?
I think not. Shamir's method requires that of the S and T
trees, at least the T tree really be there. We have to
traverse it many times and in all kinds of orders. Being
there virtually is not enough.

Finally, what about local maxima? We cannot detect local
maxima by forming Xq for a position X and for all q in Q,
testing to see of all Xq are closer to Start. (The Xq are
not in lexicographical order.) I am thinking about the
following as a way to find local maxima, but it may be
bogus. See what you think.

Suppose a position in one of the virtual Q[n+k]'s that we
are creating is not the product of any st for s in Q[n]
and t in Q[k+2]. For example, suppose there is an element
p in Q[n+1] which is not the product of any st for s in
Q[n] and t in Q[3]. (We could find all such p easily in
our scan of the virtual Q[n+k] trees.) Could we say that
all such p are local maxima? I am not sure.

This method works for sure to find local maxima in Q[n-1]
when creating Q[n+1]. In fact, this method is the way I
find local maxima with my large tape searches. That is,
the method works when you are only going one step ahead.
If you use Q[n] and Q[1] to create Q[n+1], then all the
products are in Q[n+1] or Q[n-1], and any element of
Q[n-1] which is not a product of Q[n] and Q[1] is a local
maximum. But can we say that any element of Q[n+1] that
is not a product of Q[n] and Q[3] is a local maximum? I
just don't know.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                jbryan@pstcc.cc.tn.us
Pellissippi State                            (423) 539-7127
10915 Hardin Valley Road                     (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990