|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include James D. Mitchell.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
InstallMethod(IsGeneratorsOfMagmaWithInverses,
"for a partial perm collection",
[IsPartialPermCollection],
function(coll)
return ForAll(coll, x -> DomainOfPartialPerm(x)
= DomainOfPartialPerm(coll[1])
and
ImageSetOfPartialPerm(x)
= DomainOfPartialPerm(coll[1]));
end);
# attributes
InstallMethod(DomainOfPartialPerm, "for a partial perm",
[IsPartialPerm], DOMAIN_PPERM);
InstallMethod(ImageListOfPartialPerm, "for a partial perm",
[IsPartialPerm], IMAGE_PPERM);
InstallMethod(ImageSetOfPartialPerm, "for a partial perm",
[IsPartialPerm], IMAGE_SET_PPERM);
InstallMethod(IndexPeriodOfPartialPerm, "for a partial perm",
[IsPartialPerm], INDEX_PERIOD_PPERM);
InstallMethod(SmallestIdempotentPower, "for a partial perm",
[IsPartialPerm], SMALLEST_IDEM_POW_PPERM);
InstallMethod(ComponentRepsOfPartialPerm, "for a partial perm",
[IsPartialPerm], COMPONENT_REPS_PPERM);
InstallMethod(NrComponentsOfPartialPerm, "for a partial perm",
[IsPartialPerm], NR_COMPONENTS_PPERM);
InstallMethod(ComponentsOfPartialPerm, "for a partial perm",
[IsPartialPerm], COMPONENTS_PPERM);
InstallMethod(IsIdempotent, "for a partial perm",
[IsPartialPerm], IS_IDEM_PPERM);
InstallMethod(IsOne, "for a partial perm",
[IsPartialPerm], IS_IDEM_PPERM);
InstallMethod(FixedPointsOfPartialPerm, "for a partial perm",
[IsPartialPerm], FIXED_PTS_PPERM);
InstallMethod(NrFixedPoints, "for a partial perm",
[IsPartialPerm], NR_FIXED_PTS_PPERM);
InstallMethod(MovedPoints, "for a partial perm",
[IsPartialPerm], MOVED_PTS_PPERM);
InstallMethod(NrMovedPoints, "for a partial perm",
[IsPartialPerm], NR_MOVED_PTS_PPERM);
InstallMethod(LargestMovedPoint, "for a partial perm",
[IsPartialPerm], LARGEST_MOVED_PT_PPERM);
InstallMethod(LargestImageOfMovedPoint, "for a partial perm",
[IsPartialPerm],
function(f)
local max, i;
if IsOne(f) then
return 0;
fi;
max := 0;
for i in [SmallestMovedPoint(f) .. LargestMovedPoint(f)] do
if i ^ f > max then
max := i ^ f;
fi;
od;
return max;
end);
InstallMethod(SmallestMovedPoint, "for a partial perm",
[IsPartialPerm],
function(f)
local m;
m := SMALLEST_MOVED_PT_PPERM(f);
if m = fail then
return infinity;
else
return m;
fi;
end);
InstallMethod(SmallestImageOfMovedPoint, "for a partial perm",
[IsPartialPerm],
function(f)
local min, j, i;
if IsOne(f) then
return infinity;
fi;
min := CoDegreeOfPartialPerm(f);
for i in [SmallestMovedPoint(f) .. LargestMovedPoint(f)] do
j := i ^ f;
if j > 0 and j < min then
min := j;
fi;
od;
return min;
end);
InstallMethod(LeftOne, "for a partial perm",
[IsPartialPerm], LEFT_ONE_PPERM);
InstallMethod(RightOne, "for a partial perm",
[IsPartialPerm], RIGHT_ONE_PPERM);
# operations
InstallMethod(PreImagePartialPerm,
"for a partial perm and positive integer",
[IsPartialPerm, IsPosInt and IsSmallIntRep], PREIMAGE_PPERM_INT);
InstallMethod(ComponentPartialPermInt,
"for a partial perm and positive integer",
[IsPartialPerm, IsPosInt and IsSmallIntRep], COMPONENT_PPERM_INT);
InstallGlobalFunction(JoinOfPartialPerms,
function(arg)
local join, i;
if IsPartialPermCollection(arg[1]) then
return CallFuncList(JoinOfPartialPerms, arg[1]);
elif not IsPartialPermCollection(arg) then
ErrorNoReturn("usage: the argument should be a collection of partial ",
"perms,");
fi;
join := arg[1];
i := 1;
while i < Length(arg) and join <> fail do
i := i + 1;
join := JOIN_PPERMS(join, arg[i]);
od;
return join;
end);
InstallGlobalFunction(JoinOfIdempotentPartialPermsNC,
function(arg)
local join, i;
if IsPartialPermCollection(arg[1]) then
return CallFuncList(JoinOfIdempotentPartialPermsNC, arg[1]);
elif not IsPartialPermCollection(arg) then
ErrorNoReturn("usage: the argument should be a collection of partial ",
"perms,");
fi;
join := arg[1];
i := 1;
while i < Length(arg) do
i := i + 1;
join := JOIN_IDEM_PPERMS(join, arg[i]);
od;
return join;
end);
InstallGlobalFunction(MeetOfPartialPerms,
function(arg)
local meet, i, empty;
if Length(arg) = 1 and IsPartialPermCollection(arg[1]) then
return CallFuncList(MeetOfPartialPerms, AsList(arg[1]));
elif not IsPartialPermCollection(arg) then
ErrorNoReturn("usage: the argument should be a collection of ",
"partial perms,");
fi;
meet := arg[1];
i := 1;
empty := EmptyPartialPerm();
while i < Length(arg) and meet <> empty do
i := i + 1;
meet := MEET_PPERMS(meet, arg[i]);
od;
return meet;
end);
InstallMethod(AsPartialPerm, "for a perm and a list",
[IsPerm, IsList],
function(p, list)
if not IsSSortedList(list)
or not ForAll(list, x -> IsSmallIntRep(x) and IsPosInt(x)) then
ErrorNoReturn("usage: the second argument must be a set of positive ",
"integers,");
fi;
return AS_PPERM_PERM(p, list);
end);
InstallMethod(AsPartialPerm, "for a perm",
[IsPerm], p -> AS_PPERM_PERM(p, [1 .. LargestMovedPoint(p)]));
InstallMethod(AsPartialPerm, "for a perm and pos int",
[IsPerm, IsPosInt and IsSmallIntRep],
function(p, n)
return AS_PPERM_PERM(p, [1 .. n]);
end);
InstallMethod(AsPartialPerm, "for a perm and zero",
[IsPerm, IsZeroCyc],
function(p, n)
return PartialPerm([]);
end);
# c method? JDM
InstallMethod(AsPartialPerm, "for a transformation and list",
[IsTransformation, IsList],
function(f, list)
if not IsSSortedList(list)
or not ForAll(list, x -> IsSmallIntRep(x) and IsPosInt(x)) then
ErrorNoReturn("usage: the second argument must be a set of positive ",
"integers,");
elif not IsInjectiveListTrans(list, f) then
ErrorNoReturn("usage: the first argument must be injective on the ",
"second,");
fi;
return PartialPermNC(list, OnTuples(list, f));
end);
InstallMethod(AsPartialPerm, "for a transformation and positive int",
[IsTransformation, IsPosInt and IsSmallIntRep],
function(f, n)
return AsPartialPerm(f, [1 .. n]);
end);
# n is image of undefined points
InstallMethod(AsTransformation, "for a partial perm and positive integer",
[IsPartialPerm, IsPosInt and IsSmallIntRep],
function(f, n)
local deg, out, i;
if n < DegreeOfPartialPerm(f) and n ^ f <> 0 and n ^ f <> n then
ErrorNoReturn("usage: the 2nd argument must not be a moved ",
"point of the 1st argument,");
fi;
deg := Maximum(n, LargestMovedPoint(f) + 1, LargestImageOfMovedPoint(f) + 1);
out := ListWithIdenticalEntries(deg, n);
for i in DomainOfPartialPerm(f) do
out[i] := i ^ f;
od;
return Transformation(out);
end);
InstallMethod(AsTransformation, "for a partial perm",
[IsPartialPerm],
function(f)
return AsTransformation(f,
Maximum(LargestImageOfMovedPoint(f),
LargestMovedPoint(f)) + 1);
end);
InstallMethod(RestrictedPartialPerm, "for a partial perm",
[IsPartialPerm, IsList],
function(f, list)
if not IsSSortedList(list)
or not ForAll(list, x -> IsSmallIntRep(x) and IsPosInt(x)) then
ErrorNoReturn("usage: the second argument must be a set of positive ",
"integers,");
fi;
return RESTRICTED_PPERM(f, list);
end);
InstallMethod(AsPermutation, "for a partial perm",
[IsPartialPerm], AS_PERM_PPERM);
InstallMethod(PermLeftQuoPartialPermNC, "for a partial perm and partial perm",
[IsPartialPerm, IsPartialPerm], PERM_LEFT_QUO_PPERM_NC);
InstallMethod(PermLeftQuoPartialPerm, "for a partial perm and partial perm",
[IsPartialPerm, IsPartialPerm],
function(f, g)
if ImageSetOfPartialPerm(f) <> ImageSetOfPartialPerm(g) then
ErrorNoReturn("usage: the arguments must be partial perms with equal ",
"image sets,");
fi;
return PERM_LEFT_QUO_PPERM_NC(f, g);
end);
InstallMethod(TrimPartialPerm, "for a partial perm",
[IsPartialPerm], TRIM_PPERM);
InstallMethod(PartialPermOp, "for object, list, function",
[IsObject, IsList, IsFunction],
function(f, D, act)
local perm, out, seen, i, j, pnt, new;
perm := ();
if IsPlistRep(D) and Length(D) > 2 and CanEasilySortElements(D[1]) then
if not IsSSortedList(D) then
D := ShallowCopy(D);
perm := Sortex(D);
D := Immutable(D);
fi;
fi;
out := EmptyPlist(Length(D));
seen := EmptyPlist(Length(D));
i := 0;
j := Length(D);
for pnt in D do
pnt := act(pnt, f);
new := PositionCanonical(D, pnt);
if not pnt in seen then
AddSet(seen, pnt);
if new <> fail then
i := i + 1;
out[i] := new;
else
i := i + 1;
j := j + 1;
out[i] := j;
fi;
else
return fail;
fi;
od;
out := PartialPerm([1 .. Length(D)], out);
if not IsOne(perm) then
out := out ^ perm;
fi;
return out;
end);
InstallMethod(PartialPermOp, "for an obj and list",
[IsObject, IsList],
function(obj, list)
return PartialPermOp(obj, list, OnPoints);
end);
InstallMethod(PartialPermOp, "for an obj and domain",
[IsObject, IsDomain],
function(obj, D)
return PartialPermOp(obj, Enumerator(D), OnPoints);
end);
InstallMethod(PartialPermOp, "for an obj, domain, and function",
[IsObject, IsDomain, IsFunction],
function(obj, D, func)
return PartialPermOp(obj, Enumerator(D), func);
end);
InstallMethod(PartialPermOpNC, "for object, list, function",
[IsObject, IsList, IsFunction],
function(f, D, act)
local perm, out, i, j, pnt, new;
perm := ();
if IsPlistRep(D) and Length(D) > 2 and CanEasilySortElements(D[1]) then
if not IsSSortedList(D) then
D := ShallowCopy(D);
perm := Sortex(D);
D := Immutable(D);
fi;
fi;
out := EmptyPlist(Length(D));
i := 0;
j := Length(D);
for pnt in D do
pnt := act(pnt, f);
new := PositionCanonical(D, pnt);
if new <> fail then
i := i + 1;
out[i] := new;
else
i := i + 1;
j := j + 1;
out[i] := j;
fi;
od;
out := PartialPermNC([1 .. Length(D)], out);
if not IsOne(perm) then
out := out ^ perm;
fi;
return out;
end);
InstallMethod(PartialPermOpNC, "for an obj and list",
[IsObject, IsList],
function(obj, list)
return PartialPermOpNC(obj, list, OnPoints);
end);
InstallMethod(PartialPermOpNC, "for an obj and domain",
[IsObject, IsDomain],
function(obj, D)
return PartialPermOpNC(obj, Enumerator(D), OnPoints);
end);
InstallMethod(PartialPermOpNC, "for an obj, domain, and function",
[IsObject, IsDomain, IsFunction],
function(obj, D, func)
return PartialPermOpNC(obj, Enumerator(D), func);
end);
# Creating partial perms
InstallGlobalFunction(RandomPartialPerm,
function(arg)
local source, min, max, out, seen, j, dom, img, out1, out2, i;
if Length(arg) = 1 then
if IsSmallIntRep(arg[1]) and IsPosInt(arg[1]) then
source := [1 .. arg[1]];
min := 0;
max := arg[1];
elif IsCyclotomicCollection(arg[1]) and IsSSortedList(arg[1])
and ForAll(arg[1], x -> IsSmallIntRep(x) and IsPosInt(x)) then
source := arg[1];
min := Minimum(source) - 1;
max := Maximum(source);
else
ErrorNoReturn("usage: the argument must be a positive integer, a set, ",
"or 2 sets, of positive integers, ");
fi;
out := List([1 .. max], x -> 0);
seen := BlistList([1 .. max], []);
for i in source do
j := Random(source);
if not seen[j - min] then
seen[j - min] := true;
out[i] := j;
fi;
od;
return DensePartialPermNC(out);
# for a domain and image
elif Length(arg) = 2 and IsCyclotomicCollColl(arg)
and ForAll(arg, IsSSortedList)
and ForAll(arg[1], x -> IsSmallIntRep(x) and IsPosInt(x))
and ForAll(arg[2], x -> IsSmallIntRep(x) and IsPosInt(x)) then
dom := arg[1];
img := arg[2];
out1 := EmptyPlist(Length(dom));
out2 := EmptyPlist(Length(dom));
seen := BlistList([1 .. Maximum(img)], []);
for i in dom do
j := Random(img);
if not seen[j] then
seen[j] := true;
Add(out1, i);
Add(out2, j);
fi;
ShrinkAllocationPlist(out1);
ShrinkAllocationPlist(out2);
od;
return SparsePartialPermNC(out1, out2);
else
ErrorNoReturn("usage: the argument must be a positive integer, a set, ",
"or 2 sets, of positive integers, ");
fi;
end);
InstallGlobalFunction(PartialPermNC,
function(arg)
if Length(arg) = 1 then
return DensePartialPermNC(arg[1]);
elif Length(arg) = 2 then
return SparsePartialPermNC(arg[1], arg[2]);
fi;
ErrorNoReturn("usage: there should be one or two arguments,");
end);
InstallGlobalFunction(PartialPerm,
function(arg)
if Length(arg) = 1 then
if ForAll(arg[1], i -> IsSmallIntRep(i) and i >= 0)
and IsDuplicateFreeList(Filtered(arg[1], x -> x <> 0)) then
return DensePartialPermNC(arg[1]);
else
ErrorNoReturn("usage: the argument must be a list of non-negative ",
"integers and the non-zero elements must be ",
"duplicate-free,");
fi;
elif Length(arg) = 2 then
if IsSSortedList(arg[1]) and ForAll(arg[1], IsPosInt and IsSmallIntRep)
and IsDuplicateFreeList(arg[2]) and ForAll(arg[2], IsPosInt and IsSmallIntRep)
and Length(arg[1]) = Length(arg[2]) then
return SparsePartialPermNC(arg[1], arg[2]);
else
ErrorNoReturn("usage: the 1st argument must be a set of positive ",
"integers and the 2nd argument must be a duplicate-free ",
"list of positive integers of equal length to the first");
fi;
fi;
ErrorNoReturn("usage: there should be one or two arguments, ");
end);
# printing, viewing, displaying...
InstallMethod(String, "for a partial perm",
[IsPartialPerm],
function(f)
return STRINGIFY("PartialPerm( ", DomainOfPartialPerm(f), ", ",
ImageListOfPartialPerm(f), " )");
end);
InstallMethod(PrintString, "for a partial perm",
[IsPartialPerm],
function(f)
return PRINT_STRINGIFY("PartialPerm( ",
Concatenation(PrintString(DomainOfPartialPerm(f)), ", "),
ImageListOfPartialPerm(f), " )");
end);
InstallMethod(PrintObj, "for a partial perm",
[IsPartialPerm],
function(f)
Print("PartialPerm(\>\> ", DomainOfPartialPerm(f), "\<, \>",
ImageListOfPartialPerm(f), "\<\< )");
end);
InstallMethod(ViewString, "for a partial perm",
[IsPartialPerm],
function(f)
if DegreeOfPartialPerm(f) = 0 then
return "<empty partial perm>";
fi;
if RankOfPartialPerm(f) < UserPreference("PartialPermDisplayLimit") then
if UserPreference("NotationForPartialPerms") = "component" then
if DomainOfPartialPerm(f) <> ImageListOfPartialPerm(f) then
return ComponentStringOfPartialPerm(f);
else
return PRINT_STRINGIFY("<identity partial perm on ",
DomainOfPartialPerm(f),
">");
fi;
elif UserPreference("NotationForPartialPerms") = "domainimage" then
if DomainOfPartialPerm(f) <> ImageListOfPartialPerm(f) then
return PRINT_STRINGIFY(DomainOfPartialPerm(f),
" -> ",
ImageListOfPartialPerm(f));
else
return PRINT_STRINGIFY("<identity partial perm on ",
DomainOfPartialPerm(f),
">");
fi;
elif UserPreference("NotationForPartialPerms") = "input" then
return PrintString(f);
fi;
fi;
return STRINGIFY("<partial perm on ",
Pluralize(RankOfPartialPerm(f), "pt"),
" with degree ",
DegreeOfPartialPerm(f),
", codegree ",
CoDegreeOfPartialPerm(f),
">");
end);
InstallGlobalFunction(ComponentStringOfPartialPerm,
function(f)
local n, seen, str, i, j;
n := Maximum(DegreeOfPartialPerm(f), CoDegreeOfPartialPerm(f));
seen := List([1 .. n], x -> 0);
#find the image
for i in ImageSetOfPartialPerm(f) do
seen[i] := 1;
od;
str := "";
#find chains
for i in DomainOfPartialPerm(f) do
if seen[i] = 0 then
Append(str, "\>[\>");
Append(str, String(i));
Append(str, "\<");
seen[i] := 2;
i := i ^ f;
while i <> 0 do
Append(str, ",\>");
Append(str, String(i));
Append(str, "\<");
seen[i] := 2;
i := i ^ f;
od;
Append(str, "\<]");
fi;
od;
#find cycles
for i in DomainOfPartialPerm(f) do
if seen[i] = 1 then
Append(str, "\>(\>");
Append(str, String(i));
Append(str, "\<");
j := i ^ f;
while j <> i do
Append(str, ",\>");
Append(str, String(j));
Append(str, "\<");
seen[j] := 2;
j := j ^ f;
od;
Append(str, "\<)");
fi;
od;
return str;
end);
#collections
InstallMethod(DegreeOfPartialPermCollection,
"for a partial perm collection",
[IsPartialPermCollection], coll -> Maximum(List(coll, DegreeOfPartialPerm)));
InstallMethod(CodegreeOfPartialPermCollection,
"for a partial perm collection",
[IsPartialPermCollection], coll -> Maximum(List(coll, CodegreeOfPartialPerm)));
InstallMethod(RankOfPartialPermCollection,
"for a partial perm collection",
[IsPartialPermCollection], coll -> Length(DomainOfPartialPermCollection(coll)));
InstallMethod(DomainOfPartialPermCollection, "for a partial perm coll",
[IsPartialPermCollection], coll -> Union(List(coll, DomainOfPartialPerm)));
InstallMethod(ImageOfPartialPermCollection, "for a partial perm coll",
[IsPartialPermCollection], coll -> Union(List(coll, ImageSetOfPartialPerm)));
InstallMethod(FixedPointsOfPartialPerm, "for a partial perm coll",
[IsPartialPermCollection], coll -> Union(List(coll, FixedPointsOfPartialPerm)));
InstallMethod(MovedPoints, "for a partial perm coll",
[IsPartialPermCollection], coll -> Union(List(coll, MovedPoints)));
InstallMethod(NrFixedPoints, "for a partial perm coll",
[IsPartialPermCollection], coll -> Length(FixedPointsOfPartialPerm(coll)));
InstallMethod(NrMovedPoints, "for a partial perm coll",
[IsPartialPermCollection], coll -> Length(MovedPoints(coll)));
InstallMethod(LargestMovedPoint, "for a partial perm collection",
[IsPartialPermCollection], coll -> Maximum(List(coll, LargestMovedPoint)));
InstallMethod(LargestImageOfMovedPoint, "for a partial perm collection",
[IsPartialPermCollection],
coll -> Maximum(List(coll, LargestImageOfMovedPoint)));
InstallMethod(SmallestMovedPoint, "for a partial perm collection",
[IsPartialPermCollection], coll -> Minimum(List(coll, SmallestMovedPoint)));
InstallMethod(SmallestImageOfMovedPoint, "for a partial perm collection",
[IsPartialPermCollection],
coll -> Minimum(List(coll, SmallestImageOfMovedPoint)));
InstallMethod(OneImmutable, "for a partial perm coll",
[IsPartialPermCollection],
function(x)
return JoinOfIdempotentPartialPermsNC(List(x, OneImmutable));
end);
InstallMethod(OneMutable, "for a partial perm coll",
[IsPartialPermCollection], OneImmutable);
InstallMethod(MultiplicativeZeroOp, "for a partial perm",
[IsPartialPerm], x -> PartialPerm([]));
[ Dauer der Verarbeitung: 0.32 Sekunden
(vorverarbeitet)
]
|
