/usr/share/gap/pkg/grape/lib/smallestimage.g is in gap-grape 4r7+ds-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 | ##############################################################################
##
## smallestimage.g GRAPE Library Steve Linton
##
## Copyright (C) Steve Linton 2003
##
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, see http://www.gnu.org/licenses/gpl.html
#
BindGlobal("SmallestImageSet",function(arg)
local best, h, k, n, paths, level, min, goodpaths,
orbnums, orbmins, gens, path, cands, remset, bestpt,
x, q, rep, num, pt, gen, img, besto, newpaths,
cases, case, newpath, g, set;
# Function by Steve Linton.
# Slightly modified by Leonard Soicher, and renamed from `SmallestImage'
# to `SmallestImageSet'.
# This algorithm is iterative. At level i it
# computes the lex-least i-set which can be an image
# of any subset of set, and all the essentially different ways
# in which this can happen. The lex-least image of set must arise
# by extending one of these
#
# in concrete terms, best is that i-set, h is the sequence
# stabilizer of best and paths is a list of records
#
# each record has components: mappedpts indicating which points in set
# are mapped tuple-wise onto best; remainder is set\mappedpts;
# perm is an element of g mapping mappedpts to best
# substab is a subgroup of the stabilizer of mappedpts (ptwise)
# and remainder (setwise)
# paths should contain entries with every possible sequence
# mappedpts, subject to the action of the setwise stabilizer Stab(g, set)
#
# Each iteration is done in two phases. In the first we examine
# each entry in paths to see what is the smallest point to which
# any entry of remainder^perm can be mapped by h, and which entries of
# remainder can be mapped there. We remember in goodpaths the ones that achieve
# the global smallest point, which we add to best
#
# In the second part, we take each entry on goodpaths and see what
# essentially different (under substab) ways there are to extend it
# we add those to newpaths.
if Length(arg) < 2 then
Error("SmallestImageSet: must have at least 2 parameters");
fi;
g := arg[1];
set := arg[2];
if not IsPermGroup(g) or not IsSet(set) then
Error("usage: SmallestImageSet( <PermGroup>, <Set> [, <PermGroup> ] )");
fi;
if set = [] then
return [];
fi;
set := Set(set);
if IsTrivial(g) then
return set;
fi;
best := [];
h := g;
if Length(arg) >= 3 then
k := arg[3];
if k = false then
k := Group(());
fi;
if not IsPermGroup(k) then
Error("<k> must be a permutation group");
fi;
else
k := Stabilizer(g,set,OnSets);
fi;
n := Maximum(set[Length(set)],LargestMovedPoint(g));
paths := [rec(mappedpts := [],
remainder := set,
perm := (),
substab := k)];
for level in [1..Length(set)] do
if Size(h) = 1 then
Append(best, Minimum(List(paths, path -> OnSets(path.remainder, path.perm))));
return best;
fi;
min := infinity;
goodpaths := [];
orbnums := ListWithIdenticalEntries(n,-1);
orbmins := [];
gens := GeneratorsOfGroup(h);
for path in paths do
if Size(path.substab) = 1 then
cands := path.remainder;
else
cands := List(OrbitsDomain(path.substab, path.remainder), o->o[1]);
fi;
remset := OnTuples(cands,path.perm);
#
# We need to decide the smallest image of anything in remset
# under h. We build up a orbit numbers data structure
# lazily so that we only do the orbit calculations we need
# and only do them once.
#
bestpt := infinity;
for x in remset do
if orbnums[x] = -1 then
#
# Need a new orbit. Also require the smallest point
# as the rep.
#
q := [x];
rep := x;
num := Length(orbmins)+1;
orbnums[x] := num;
for pt in q do
for gen in gens do
img := pt^gen;
if orbnums[img] = -1 then
orbnums[img] := num;
Add(q,img);
if img < rep then
rep := img;
fi;
fi;
od;
od;
orbmins[num] := rep;
else
num := orbnums[x];
rep := orbmins[num];
fi;
#
# Does this help?
#
if rep < bestpt then
besto := num;
bestpt := rep;
fi;
od;
if bestpt < min then
#
# Improved the global bound, forget all previous candidates
#
goodpaths := [];
min := bestpt;
fi;
if bestpt = min then
#
# rmemeber this case
#
path.relevant := Filtered(path.remainder, x->
orbnums[x^path.perm] = besto);
Add(goodpaths, path);
fi;
od;
#
# Here goodpaths contains the options that need further exploration.
# min is the next point in the smallest image
#
Add(best,min);
if level = Length(set) then
return best;
fi;
newpaths := [];
for path in goodpaths do
#
# We can reduce the search by using some residual symmetry
#
if IsTrivial(path.substab) then
cases := path.relevant;
else
cases := List(Orbits(path.substab,path.relevant), o->o[1]);
fi;
for case in cases do
newpath := StructuralCopy(path);
Add(newpath.mappedpts,case);
#
# use Representative action this way round so that the
# non-changing point is first. Dramatically reduces the number
# of base changes
newpath.perm := newpath.perm / RepresentativeAction(h,min,case^path.perm);
RemoveSet(newpath.remainder,case);
newpath.substab := Stabilizer(newpath.substab,case);
Add(newpaths, newpath);
od;
od;
paths := newpaths;
h := Stabilizer(h,min);
od;
end);
|