\datethis
\def\SET/{{\mc SET\null}}
@*Introduction. This program finds all nonisomorphic sets of \SET/ cards
that contain no \SET/s.
In case you don't know what that means, a \SET/ card is a vector
$(c_1,c_2,c_3,c_4)$ where each $c_i$ is 0, 1, or~2. Thus there are 81
possible \SET/ cards. A~\SET/ is a set of three \SET/ cards that sums
to $(0,0,0,0)$ modulo~3. Equivalently, the numbers in each coordinate
position of the three vectors in a \SET/ are either all the same or all
different. (It's kind of a 4-dimensional tic-tac-toe with wraparound.)
My previous {\sc SETSET} program considered only isomorphisms that
apply directly to the semantics of the game of \SET/, namely
permutations of coordinates and permutations of individual coordinate
positions; there are $4!\times 3!^4=31104$ of those. But now I want
to consider the much larger collection of all isomorphisms that
preserve \SET/s. There are $81\cdot(81-1)\cdot(81-3)\cdot(81-9)\cdot(81-27)
=1{,}965{,}150{,}720$ of these; thus the method used in the
previous program, which had complexity $\Omega(\hbox{number of isomorphisms})$
in both time and space, would be quite inappropriate. Here I'm using
a possibly new method, with space requirement only
$O(\hbox{number of elements})^2D$, where $D$ bounds the partial
transitivity of the isomorphism group: The image of the first $D$ elements
is sufficient to determine the images of all. In our case, $D=5$.
A web page of David Van Brink states that you can't have more than 20 \SET/
cards without having a \SET/. He says that he proved this in 1997 with a
computer program that took about one week to run on a 90MHz Pentium machine.
I'm hoping to get the result faster by using ideas of isomorph rejection,
meanwhile also discovering all of the $k$-element \SET/-less solutions
for $k\le20$.
The theorem about at most 20 \SET/-free cards was actually proved in much
stronger form by G. Pellegrino, {\sl Matematiche\/ \bf25} (1971), 149--157,
without using computers. Pellegrino showed that any set of 21 points in
the projective space of $81+27+9+3+1$ elements, represented by nonzero
5-tuples in which $x$ and $-x$ are considered equivalent, has three
collinear points; this would correspond to sets of three distinct points
in which the third is the sum or difference of the first two.
Incidentally, I've written this program for my own instruction, not for
publication. I~still haven't had time to read the highly relevant
papers by Adalbert Kerber, Reinhard Laue, and their colleagues at Bayreuth,
@^Kerber, Adalbert@>
@^Laue, Reinhard@>
although I've
had those works in my files for many years. Members of that group
probably are quite familiar with equivalent or better methods.
Perhaps I'm being foolish, but I thought it would be most educational to try
my own hand before looking at other people's solutions. I seem to learn a new
subject best when I try to write code for it, because the computer is
such a demanding, unbluffable taskmaster.
[\SET/ is a registered trademark of SET Enterprises, Inc.]
@c
#include
#include
#include
jmp_buf restart_point;
@@;
@@;
@@;
@#
main()
{
@@;
@;
@;
@;
}
@ Our basic approach is to define a linear ordering on solutions, and to
look only for solutions that are smallest in their isomorphism class.
In other words, we will count the sets $S$ such that $S\le\alpha S$ for
all automorphisms~$\alpha$. We'll also count the number $t$ of cases where
$S=\alpha S$; then the number of distinct solutions isomorphic to~$S$
is $1965150720/t$, so we will essentially have also enumerated the distinct
solutions.
The ordering we use is almost standard: Vectors are ordered
by weight, and vectors of equal weight are ordered lexicographically;
thus the sequence is $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(0,1,0,0)$,
$(1,0,0,0)$, $(0,0,0,2)$, $(0,0,1,1)$, \dots, $(2,2,2,2)$.
Also, when $S$ and $T$ are both sets of $k$ \SET/ cards, we define
$S\le T$ by first sorting the vectors into order so that $s_1<\cdots=
typedef char SETcard; /* a \SET/ card $(c_1,c_2,c_3,c_4)$
represented as $|encode|[(c_1 c_2 c_3 c_4)_3]$ */
@ Lexicographic order would correspond
to ternary notation, but our weight-first ordering is slightly different.
Here we specify the card ranks in the desired order.
@d nn 81 /* the total number of elements permuted by automorphisms */
@d nnn 128 /* the value of |nn| rounded up to a power of 2, for efficiency */
@=
SETcard encode[nn]={0,1,5,2,6,15,7,16,31,@|
3,8,17,9,18,32,19,33,50,@|
10,20,34,21,35,51,36,52,66,@|
4,11,22,12,23,37,24,38,53,@|
13,25,39,26,40,54,41,55,67,@|
27,42,56,43,57,68,58,69,76,@|
14,28,44,29,45,59,46,60,70,@|
30,47,61,48,62,71,63,72,77,@|
49,64,73,65,74,78,75,79,80};
@ When we output a \SET/ card, however, we prefer a decimal code.
@=
int decimalform[nn]={
0,1,2,10,11,12,20,21,22,@|
100,101,102,110,111,112,120,121,122,@|
200,201,202,210,211,212,220,221,222,@|
1000,1001,1002,1010,1011,1012,1020,1021,1022,@|
1100,1101,1102,1110,1111,1112,1120,1121,1122,@|
1200,1201,1202,1210,1211,1212,1220,1221,1222,@|
2000,2001,2002,2010,2011,2012,2020,2021,2022,@|
2100,2101,2102,2110,2111,2112,2120,2121,2122,@|
2200,2201,2202,2210,2211,2212,2220,2221,2222};
int decode[nn];
@ @=
for (k=0;k=
char z[3][3]={{0,2,1},{2,1,0},{1,0,2}}; /* $x+y+z\equiv0$ (mod 3) */
char third[nn][nnn];
@ @d pack(a,b,c,d) encode[(((a)*3+(b))*3+(c))*3+(d)]
@=
{
int a,b,c,d,e,f,g,h;
for (a=0;a<3;a++) for (b=0;b<3;b++) for (c=0;c<3;c++) for (d=0;d<3;d++)
for (e=0;e<3;e++) for (f=0;f<3;f++) for (g=0;g<3;g++) for (h=0;h<3;h++)
third[pack(a,b,c,d)][pack(e,f,g,h)]= pack(z[a][e],z[b][f],z[c][g],z[d][h]);
}
@ The set of automorphisms is conveniently represented by a mapping
table, as in the author's paper ``Efficient representation of
perm groups,'' {\sl Combinatorica\/ \bf11} (1991), 33--43.
If there is an $\alpha$ such that $\alpha k=j$ and $\alpha$ fixes
all elements~$
pointing out a serious error. However, I do think the special group dealt
with here is handled satisfactorily because of its highly transitive nature.
@d dd 5 /* in our case $D=5$ */
@=
char perm[dd][nnn][nnn]; /* mapping table */
@ Now let's set up the mapping table for the affine transformations we need.
The basic idea is simple. For example, the group of all $5\times 5$ matrices
that fix $(0,0,0,0)=0$ and $(0,0,0,1)=1$ is the set of all nonsingular~$A$
of the form
$$\pmatrix{\ast&\ast&\ast&0&0\cr
\ast&\ast&\ast&0&0\cr
\ast&\ast&\ast&0&0\cr
\ast&\ast&\ast&1&0\cr
0 & 0 & 0 &0&1\cr}\,;$$
and the image of $(0,0,1,0)$ is the third column. For every possible third
column~$k$ (which must not be zero in the top three rows, lest the matrix be
singular), we need to choose an appropriate setting of the first two columns.
Then we get an affine mapping that takes $(0,0,1,0)=2$ into $k$, and
the inverse of this mapping can be stored in |perm[2][k]| because it
maps $k\mapsto2$.
@=
aa[4][4]=1;
for (j=0;j<5;j++) { /* we want to set up |perm[4-j]| */
int a,b,c,d,e,f,g,h,jj,kk;
for (jj=j+1;jj<5;jj++) for (k=0;k<4;k++) aa[jj][k]=(k==jj? 1: 0);
for (a=0;a<3;a++) for (b=0;b<3;b++) for (c=0;c<3;c++) for (d=0;d<3;d++) {
aa[j][0]=a, aa[j][1]=b, aa[j][2]=c, aa[j][3]=d;
for (kk=j; kk>=0; kk--) if (aa[j][kk]) break;
if (kk<0) perm[4-j][pack(a,b,c,d)][0]=-1;
else {
@;
@