gsf wrote:gsf wrote:the number of automorphisms for any grid is in the range 1..648 inclusive

do we know the impossible ones (number of automorphisms) in that range?

having the catalog in hand is ... handy

here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms

- Code: Select all
` 1 5472170387`

2 548449

3 7336

4 2826

6 1257

8 29

9 42

12 92

18 85

27 2

36 15

54 11

72 2

108 3

162 1

648 1

You might have seen my post from

November 2005 which leads to the same list as yours.

I see by the way that you have created the grids in compressed form. I think it should be possible with i little bit more than 2 bits/grid (uncomporessed, but I don't think compression will be significant), but I don't know how fast you expect the program that gets the grid to be. And you can't have the grids ordered in whatever way you like - actually they are forced in a very rigid order.

This is how:

First, index the 44 column configuration classes of the bands. Then index the 416 band classes, at least sorted by the configuration index.

Now, the grids are first sorted by the 416-index of the top band. With the top band on its place, we run through the 56*56*56 possible choices for the column configuration of band 2 and 3, and skip those where the 44-index of band 2 and 3 are smaller than the index of band 1 - or when the index of band 3 is smaller than the one for band 2. Then we can run through the possible bands for the configuration of band 2 and 3. For each choice, we need one single bit telling whether this is a grid representing its class or not. Almost 50% (*) of the grids are representing its class, that's why we need 2 bits for each class.

A lookup dictionary for the 416*56*56*56 cases will help us rapidly find the place to look for our grid. Getting all bands from a configuration is fast, it takes me 0.0025 seconds for all 44 configurations on 3 GHz, including generation of lookup tables.

(*) beacuse almost every grid (19999 out of 20000) has a trivial automorphism group, so the representation mentioned above will in general visit every class twice; the representative and some transposed grid. Ironically, if a grid is not identified with it's transposed, we get about twice as many classes (10945437157), but this time the here mentioned method would give a bit stream with basically ones. If we replace the stream with the leap sizes from one zero to another, we might need less than 1 bit/grid!