From @uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu Fri Feb 23 00:39:22 1996
Return-Path: <@uconnvm.uconn.edu:dmoews@xraysgi.ims.uconn.edu>
Received: from UConnVM.UConn.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06036; Fri, 23 Feb 96 00:39:22 EST
Received: from venus.ims.uconn.edu by UConnVM.UConn.Edu (IBM VM SMTP V2R2)
with TCP; Fri, 23 Feb 96 00:39:17 EST
Received: from xraysgi.ims.uconn.edu by venus.ims.uconn.edu (4.1/SMI-4.1)
id AA04295; Thu, 22 Feb 96 16:36:36 EST
Received: by xraysgi.ims.uconn.edu (931110.SGI/911001.SGI)
for @venus.ims.uconn.edu:cube-lovers@life.ai.mit.edu id AA10513; Fri, 23 Feb 96 00:39:02 -0500
Date: Fri, 23 Feb 96 00:39:02 -0500
From: dmoews@xraysgi.ims.uconn.edu (David Moews)
Message-Id: <9602230539.AA10513@xraysgi.ims.uconn.edu>
To: cube-lovers@life.ai.mit.edu, dmoes@xraysgi.ims.uconn.edu
Subject: Implementing Shamir's method
Since there seems to be a surge of interest in Shamir's method, I
thought I would mention a few points about it and my implementation
of it:
1. How the group must be represented in order to use Shamir's method.
We suppose that elements of our group G are represented by ordered
tuples, which can be ordered lexicographically; we want to generate
the list ST in this lexicographical order. Suppose that we have an element
s of S, and elements t and u in T which first differ in coordinate i. For
Shamir's method to work, we need to be able to order st and su given
only the length i initial segments of t and u. This is true for
permutation groups if we represent them as acting on {1,...,n}
(st compares to su as s(t(i)) compares to s(u(i)).)
It is also true for the wreath products occurring in the cube group:
suppose G = H wr K, where H is a permutation group acting on {1,...,n},
and K is a product of cyclic groups with index set {1,...,n}. Then
if we write an element g of G as ( g(1), ..., g(n), g'(1), ..., g'(n) ),
the g(i)'s being in {1,...,n} and the g'(i)'s in the cyclic groups,
we can write
( h(1), ..., h(n), h'(1), ..., h'(n) ) ( k(1), ..., k(n), k'(1), ..., k'(n) )
=
( h(k(1)), ..., h(k(n)), h'(k(1)) + k'(1), ..., h'(k(n)) + k'(n) ).
Hence if t and u's first difference is in t(i) != u(i), st and su compare
as s(t(i)) and s(u(i)), and if t and u's first difference is in t'(i) != u'(i),
st and su compare as s'(t(i)) + t'(i) and s'(u(i)) + u'(i).
Since you do a lot of composition in Shamir's method, I felt it best to
leave the permutations unpacked. I used the wreath product representation
above, with H = S_8 x S_12 and K = (Z/3Z)^8 x (Z/2Z)^12. Each permutation
then used 8 + 12 + 8 + 12 = 40 bytes. All members of both S and T must be
stored in memory (see below.) This used up a lot of memory. (You could,
of course, also represent the cube group as a permutation group on the 48
facelets.)
2. The data structure for T.
Jerry Bryan has alluded to this. I used a tree each of whose leaves
contained a member of T, and each of whose internal nodes contained
an index indicating which tuple coordinate was being branched on, a
value of this coordinate for each son, and pointers to each son.
I also included a pointer to the father to make traversal easier.
The data structure for T does not change during the algorithm; you
can use it with more than one S at once.
3. The data structure for S.
By traversing the T tree approriately, we can output the sequence
X(s) = (lexicographical sort of {st | t in T}) for each s. For all elements s
of S, we need to store s itself, and a marker to show our position in X(s)
(for me, this was just a pointer to the T tree.)
We also need enough structure to make merging the X(s)'s easy. I used a
`tree of losers' (cf. Knuth, Chapter 5.) Since there seems to be
some uncertainty about this, I will go into detail. Let S = {s_0, ..., s_(N-1)}.
The tree will then have 2N nodes: N internal ones, 0 through N-1, and N
leaves, N through 2N-1. Each internal node i contains a pointer to a leaf.
The leaves contain the actual s_j's, as well as the pointers to T. Node i
has nodes 2i and 2i+1 as sons if 0* 0 do
if the next element of X(s_a_0) is greater than the next
element of X(s_a_i)
then swap a_i and a_0 (we have a new loser)
i := floor(i/2)
od
As you see, we perform many comparisons between the first elements of the
X(s_i)'s. It is convenient to store the next element of X(s_i) in
the data structure with s_i. This uses up much more memory (a comparable
amount with that taken by S and T themselves) but does speed up the program
somewhat.
--
David Moews dmoews@xraysgi.ims.uconn.edu
*