From: Dave Rusin <rusin@math.niu.edu>
Date: Thu, 9 Jul 1998 02:33:13 -0500 (CDT)
To: bicat@capescott.net
Subject: Re: Spacial Relations Experts - I need help
Newsgroups: sci.math

In article <899591157.68383@nnrp.gt.ca> you write:

>There are 2 shapes that result from 3 cubes:
>4 cubes can easily be found to have 8 possible shapes.
>5 cubes can be found to have 25 shapes.
>6 cubes make at least 112 shapes.

>Can anyone come up with a method to calculate y shapes given
>x cubes, whether using an elegant proof or a brutal try all the
>combinations with a BASIC program method?

Elegant? probably not, although you might want to check the literature
about enumerating hydrocarbon isomers etc. to see if someone has
done this.

Brute force? Well, if you think you know all the shapes of size  N,
place each in space so that the center of each cell is at an integer point.
Then we get all the shapes of size  N+1:

for each old shape
 for each cell in it (N)
  for each face of that cell (6)
   add a new cell there and store in a big list
  next
 next
next
for each new shape
 for each new shape earlier on the big list
  if the new shapes are congruent, toss the later one
 next
 if not tossed, it's really new; save in another list
next
end

If there are really 25 shapes when N=5, then you'll consider at most
25x5x6 = 750 new shapes for N=6, which is nice and small. Even in the
second loop you then have no more than 750^2 comparisons to make
(surely much less than the 50 000 this suggests), which is again no big deal.

The hardest part is going to be deciding when two shapes  A, B  are the same.
One method would be:

fix an ordering of the cells of  A  and  B
for each cell of  B,  (N+1)
 for each orientation of a cell (24)
  translate A so that its first cell lies in the chosen cell of B, and then
	apply the chosen translation
  check the other cells of  A  to see if they equal the cells of B
  when all do, declare a match and quit; otherwise
 next orientation
next cell
If we haven't declared a match yet, then  A  and  B  aren't the same.

However, it's sure to be more efficient to store, for each shape, some minimal
geometric or graph-theoretic information; this can give a quick "no" vote when
deciding whether two shapes are the same. For example, we could store for
each shape various numbers: how many cells have a unique neighbor ("ends")?
How many have 2, 3, 4, ... neighbors? How many total face-to-face gluings are 
there? Is the shape all in a line, or all in one plane, or only 3D? etc.

The point here is that if you have to compare  M  items (you're looking at
at least M = 112, right?) then the little program I wrote requires about
M^2 comparisons -- and not particularly quick ones at that. On the other hand,
if you collect a lot of data about each shape just once, (costs you about
k x M  time), then the shapes can be pre-sorted e.g. according to the number of
"ends", and then the number of shapes which have to be compared manually
is much faster.  Even if  k  is pretty large,  k x M  will be less than 
M^2  for such big  M.

I'd be curious to know what you find out if you try this.

dave