gap-libs 4r7p9-1 / usr / share / gap / lib / pperm.gi

#############################################################################
##
#W  pperm.gi
##Y  Copyright (C) 2011-13                                James D. Mitchell
##
###  Licensing information can be found in the README file of this package.
##
#############################################################################
##

InstallTrueMethod(IsGeneratorsOfInverseSemigroup, IsPartialPermCollection);

#

InstallMethod(IsGeneratorsOfMagmaWithInverses,
 "for a partial perm collection",
[IsPartialPermCollection],
coll-> ForAll(coll, x-> DomainOfPartialPerm(x)=DomainOfPartialPerm(coll[1]) and
ImageSetOfPartialPerm(x)=DomainOfPartialPerm(coll[1])));

# 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)
  if IsOne(f) then
    return infinity;
  fi;
  return SMALLEST_MOVED_PT_PPERM(f);
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], PREIMAGE_PPERM_INT);

#

InstallMethod(ComponentPartialPermInt,
"for a partial perm and positive integer",
[IsPartialPerm, IsPosInt], 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 
    Error("usage: the argument should be a collection of partial perms,");
    return;
  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 
    Error("usage: the argument should be a collection of partial perms,");
    return;
  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;

  if IsPartialPermCollection(arg[1]) then 
    return CallFuncList(MeetOfPartialPerms, AsList(arg[1]));
  elif not IsPartialPermCollection(arg) then 
    Error("usage: the argument should be a collection of partial perms,");
    return;
  fi;

  meet:=arg[1]; i:=1;
  repeat
    i:=i+1;
    meet:=MEET_PPERMS(meet, arg[i]);
  until i=Length(arg) or meet=EmptyPartialPerm();
    
  return meet;
end);

#

InstallMethod(AsPartialPerm, "for a perm and a list", 
[IsPerm, IsList], 
function(p, list)
  
  if not IsSSortedList(list) or not ForAll(list, IsPosInt) then 
    Error("usage: the second argument must be a set of positive integers,");
    return;
  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], 
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, IsPosInt) 
    or not ForAll(list, i-> i<=DegreeOfTransformation(f)) then 
    Error("usage: the second argument must be a set of positive integers ", 
    "not greater than the degree of the first argument,");
    return;
  elif not IsInjectiveListTrans(list, f) then 
    Error("usage: the first argument must be injective on the second,");
    return fail;
  fi;
  return PartialPermNC(list, OnTuples(list, f)); 
end);

#

InstallMethod(AsPartialPerm, "for a transformation and positive int",
[IsTransformation, IsPosInt], 
function(f, n)
  return AsPartialPerm(f, [1..n]);
end);

# c method? JDM

InstallMethod(AsPartialPerm, "for a transformation", 
[IsTransformation],
function(f)
  local img, n;
  n:=DegreeOfTransformation(f);
  if not n^f=n then 
    return fail; 
  fi;
  return PartialPerm(List([1..n], function(i) 
    local j;
    j:=i^f;
    if j=n then 
      return 0; 
    else 
      return j; 
    fi;
  end));
end);

# n is image of undefined points 
InstallMethod(AsTransformation, "for a partial perm and positive integer",
[IsPartialPerm, IsPosInt],
function(f, n)
  local deg, out, i;
  
  if n<DegreeOfPartialPerm(f) and n^f<>0 and n^f<>n then 
    Error("usage: the 2nd argument must not be a moved point of the 1st ", 
    "argument,");
    return;
  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);

# c method? JDM

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, IsPosInt) then 
    Error("usage: the second argument must be a set of positive integers,");
    return;
  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 
    Error("usage: the arguments must be partial perms with equal image sets,");
    return;
  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);
      SetIsSSortedList(D, true);
    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);
      SetIsSSortedList(D, true);
    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, n, out, seen, j, dom, img, out1, out2, i;

  if Length(arg)=1 then 
    if 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], IsPosInt) then 
      source:=arg[1];
      n:=Length(source);
      min:=Minimum(source)-1;
      max:=Maximum(source);
    else
      Error("usage: the argument must be a positive integer, a set, ",
      "or 2 sets, of positive integers,");
      return;
    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], IsPosInt) 
   and ForAll(arg[2], IsPosInt) 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 
    Error("usage: the argument must be a positive integer, a set, ",
     "or 2 sets, of positive integers,");
    return;
  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; 
 
  Error("usage: there should be one or two arguments,"); 
  return; 
end); 

#

InstallGlobalFunction(PartialPerm,
function(arg) 
   
  if Length(arg)=1 then  
    if ForAll(arg[1], i-> i=0 or IsPosInt(i)) and 
      IsDuplicateFreeList(Filtered(arg[1], x-> x<>0)) then 
      return DensePartialPermNC(arg[1]); 
    else
      Error("usage: the argument must be a list of non-negative integers ", 
      "and the non-zero elements must be duplicate-free,");
      return;
    fi;
  elif Length(arg)=2 then  
    if IsSSortedList(arg[1]) and ForAll(arg[1], IsPosInt) and
     IsDuplicateFreeList(arg[2]) and ForAll(arg[2], IsPosInt) then 
      return SparsePartialPermNC(arg[1], arg[2]); 
    else
      Error("usage: the 1st argument must be a set of positive integers ",
      "and the 2nd argument must be a duplicate-free list of positive ",
      "integers");
      return;
    fi;
  fi; 
 
  Error("usage: there should be one or two arguments,"); 
  return; 
end); 

# printing, viewing, displaying...

InstallMethod(String, "for a partial perm", 
[IsPartialPerm], 
function(f)
  return STRINGIFY("PartialPermNC( ", DomainOfPartialPerm(f), ", ",
   ImageListOfPartialPerm(f), " )");
  return;
end);

#

InstallMethod(PrintString, "for a partial perm",
[IsPartialPerm], 
function(f)
  return PRINT_STRINGIFY("PartialPermNC( ",
    Concatenation(PrintString(DomainOfPartialPerm(f)), ", "),
     ImageListOfPartialPerm(f), " )");
  return;
end);

#

InstallMethod(PrintObj, "for a partial perm",
[IsPartialPerm], 
function(f)
  Print("PartialPerm(\>\> ", DomainOfPartialPerm(f), "\<, \>",
     ImageListOfPartialPerm(f), "\<\< )");
  return;
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;
      return;
    elif UserPreference("NotationForPartialPerms")="input" then 
      return PrintString(f);
    fi;
  fi;
  
  return STRINGIFY("<partial perm on ", RankOfPartialPerm(f), 
   " pts 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(MovedPoints(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)));

InstallOtherMethod(One, "for a partial perm coll", 
[IsPartialPermCollection], 
function(x)
  return JoinOfIdempotentPartialPermsNC(List(x, One)); 
end);

InstallOtherMethod(OneMutable, "for a partial perm coll", 
[IsPartialPermCollection], 
function(x)
  return JoinOfIdempotentPartialPermsNC(List(x, One)); 
end);

#

InstallOtherMethod(ZeroMutable, "for a partial perm coll",
[IsPartialPermCollection], MeetOfPartialPerms);

#EOF