summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/unfinished/group.gap
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/group.gap')
-rw-r--r--apps/plugins/puzzles/src/unfinished/group.gap97
1 files changed, 97 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/group.gap b/apps/plugins/puzzles/src/unfinished/group.gap
new file mode 100644
index 0000000000..280adf4664
--- /dev/null
+++ b/apps/plugins/puzzles/src/unfinished/group.gap
@@ -0,0 +1,97 @@
1# run this file with
2# gap -b -q < /dev/null group.gap | perl -pe 's/\\\n//s' | indent -kr
3
4Print("/* ----- data generated by group.gap begins ----- */\n\n");
5Print("struct group {\n unsigned long autosize;\n");
6Print(" int order, ngens;\n const char *gens;\n};\n");
7Print("struct groups {\n int ngroups;\n");
8Print(" const struct group *groups;\n};\n\n");
9Print("static const struct group groupdata[] = {\n");
10offsets := [0];
11offset := 0;
12for 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);
87od;
88Print("};\n\nstatic const struct groups groups[] = {\n");
89Print(" {0, NULL}, /* trivial case: 0 */\n");
90Print(" {0, NULL}, /* trivial case: 1 */\n");
91n := 2;
92for i in [1..Size(offsets)-1] do
93 Print(" {", offsets[i+1] - offsets[i], ", groupdata+",
94 offsets[i], "}, /* ", i+1, " */\n");
95od;
96Print("};\n\n/* ----- data generated by group.gap ends ----- */\n");
97quit;