diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/unfinished/group.gap | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/group.gap')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/group.gap | 97 |
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 | |||
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; | ||