On 02/22/95 at 18:28:13 mreid@ptc.com said:

i think this can be done much more efficiently. well, at least if you
set things up properly in the first place.

suppose that you use an order (for sorting positions) in which the corner
configuration is more significant than the edge configuration.

Unfortunately, I made the edge more significant for sorting than the
corner. I plan to change that in the near future.

Strictly speaking, it would not be *too* bad to simply sort the same
data in a different order. But the problem is worse than that. I also
made the edge more significant for choosing a representative element
than the corner. So I need a new representative element function
to make the corner more significant for choosing the representative
element. Such a change to the program would be trivial, but I would
have to regenerate the data before it was re-sorted. Otherwise, the
"same" corner configuration would not be the same; equivalent corner
configurations would be M-conjugate rather than equal.

then, for each position X on your huge list, you need to check if
repr(X superflip) is on the list. since superflip only affects edges,
the corner configuration of X superflip is the same as that of X.
thus the same holds for repr(X superflip) and repr(X) = X. therefore,
you only need to look for repr(X superflip) nearby in the sorted list.

Mike's note raises several interesting points.

Suppose we write a cube Z as the disjoint union XY of corners X and
edges Y. (We could say something like Z[C,E] = Z[C]*Z[E], but let's
keep the notation a little simpler). A list of cubes in my data
base would then look something like:

X1 Y3
X1 Y7
X1 Y8
X2 Y1
X2 Y2
X2 Y5
 etc.

If we were sufficiently clever, we might be able to save some space
by rewriting the list as something like:

X1 Y3
   Y7
   Y8
X2 Y1
   Y2
   Y5
 etc.

In other words, store each corner position only one time. This is
very similar to some of the indexing schemes that have been described
to store large numbers of cubes very compactly. I have used some of
these indexing schemes for corners only or edges only, but I have
always rejected them for whole cubes (corners plus edges) because
the representation is so sparse close to Start. (and you really can't
get very far away from Start with whole cubes!) But the picture above
just might work. I'm going to think about it.

Next, notice that Mike's proposal for dealing with Pons Asinorum and
Superflip results in a cube and its neighbor being stored
very close together in the data base. In this case, a "neighbor"
is a position Z composed with Pons Asinorum or Superflip or both.
More typically, a neighbor is a position Z composed with an element
from Q or from Q+H.

What would be really nice (and which may not be possible) is some
representation for the cube such that a cube Z and its neighbors
Zq or Zh are stored very close together. Such a representation
would be very helpful in particular for searches accomplished with
massively parallel machines or with farms of workstations. But I
certainly have never been able to find such a representation.
I have yet to fully understand the Sims table (or FHL table) that
many of you seem to use, so I don't know if it will do the trick
or not.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                        (304) 293-5192
Associate Director, WVNET                            (304) 293-5540 fax
837 Chestnut Ridge Road                              BRYAN@WVNVM
Morgantown, WV 26505                                 BRYAN@WVNVM.WVNET.EDU