mdw@git.distorted.org.uk Git - sgt/puzzles/blob - unfinished/group.gap

   1 # run this file with
   2 #   gap -b -q < /dev/null group.gap | perl -pe 's/\\\n//s' | indent -kr
   3
   4 Print("/* ----- data generated by group.gap begins ----- */\n\n");
   5 Print("struct group {\n    unsigned long autosize;\n");
   6 Print("    int order, ngens;\n    const char *gens;\n};\n");
   7 Print("struct groups {\n    int ngroups;\n");
   8 Print("    const struct group *groups;\n};\n\n");
   9 Print("static const struct group groupdata[] = {\n");
  10 offsets := [0];
  11 offset := 0;
  12 for n in [2..26] do
  13   Print("    /* order ", n, " */\n");
  14   for G in AllSmallGroups(n) do
  15
  16     # Construct a representation of the group G as a subgroup
  17     # of a permutation group, and find its generators in that
  18     # group.
  19
  20     # GAP has the 'IsomorphismPermGroup' function, but I don't want
  21     # to use it because it doesn't guarantee that the permutation
  22     # representation of the group forms a Cayley table. For example,
  23     # C_4 could be represented as a subgroup of S_4 in many ways,
  24     # and not all of them work: the group generated by (12) and (34)
  25     # is clearly isomorphic to C_4 but its four elements do not form
  26     # a Cayley table. The group generated by (12)(34) and (13)(24)
  27     # is OK, though.
  28     #
  29     # Hence I construct the permutation representation _as_ the
  30     # Cayley table, and then pick generators of that. This
  31     # guarantees that when we rebuild the full group by BFS in
  32     # group.c, we will end up with the right thing.
  33
  34     ge := Elements(G);
  35     gi := [];
  36     for g in ge do
  37       gr := [];
  38       for h in ge do
  39         k := g*h;
  40         for i in [1..n] do
  41           if k = ge[i] then
  42             Add(gr, i);
  43           fi;
  44         od;
  45       od;
  46       Add(gi, PermList(gr));
  47     od;
  48
  49     # GAP has the 'GeneratorsOfGroup' function, but we don't want to
  50     # use it because it's bad at picking generators - it thinks the
  51     # generators of C_4 are [ (1,2)(3,4), (1,3,2,4) ] and that those
  52     # of C_6 are [ (1,2,3)(4,5,6), (1,4)(2,5)(3,6) ] !
  53
  54     gl := ShallowCopy(Elements(gi));
  55     Sort(gl, function(v,w) return Order(v) > Order(w); end);
  56
  57     gens := [];
  58     for x in gl do
  59       if gens = [] or not (x in gp) then
  60         Add(gens, x);
  61         gp := GroupWithGenerators(gens);
  62       fi;
  63     od;
  64
  65     # Construct the C representation of the group generators.
  66     s := [];
  67     for x in gens do
  68       if Size(s) > 0 then
  69         Add(s, '"');
  70         Add(s, ' ');
  71         Add(s, '"');
  72       fi;
  73       sep := "\\0";
  74       for i in ListPerm(x) do
  75         chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  76         Add(s, chars[i]);
  77       od;
  78     od;
  79     s := JoinStringsWithSeparator(["    {", String(Size(AutomorphismGroup(G))),
  80                                    "L, ", String(Size(G)),
  81                                    ", ", String(Size(gens)),
  82                                    ", \"", s, "\"},\n"],"");
  83     Print(s);
  84     offset := offset + 1;
  85   od;
  86   Add(offsets, offset);
  87 od;
  88 Print("};\n\nstatic const struct groups groups[] = {\n");
  89 Print("    {0, NULL}, /* trivial case: 0 */\n");
  90 Print("    {0, NULL}, /* trivial case: 1 */\n");
  91 n := 2;
  92 for i in [1..Size(offsets)-1] do
  93   Print("    {", offsets[i+1] - offsets[i], ", groupdata+",
  94         offsets[i], "}, /* ", i+1, " */\n");
  95 od;
  96 Print("};\n\n/* ----- data generated by group.gap ends ----- */\n");
  97 quit;