54 Partial permutations
  
  This chapter describes the functions in GAP for partial permutations.
  
  A partial permutation in GAP is simply an injective function from any finite
  set  of  positive integers to any other finite set of positive integers. The
  largest point on which a partial permutation can be defined, and the largest
  value  that  the  image  of  such  a  point can have, are defined by certain
  architecture dependent limits.
  
  Every  inverse  semigroup  is  isomorphic to an inverse semigroup of partial
  permutations  and,  as  such,  partial permutations are to inverse semigroup
  theory  what  permutations  are  to  group theory and transformations are to
  semigroup  theory.  In  this  way,  partial permutations are the elements of
  inverse partial permutation semigroups.
  
  A  partial  permutations in GAP acts on a finite set of positive integers on
  the right. The image of a point i under a partial permutation f is expressed
  as  i^f  in  GAP.  This  action is also implemented by the function OnPoints
  (41.2-1).  The  preimage of a point i under the partial permutation f can be
  computed   using   i/f  without  constructing  the  inverse  of  f.  Partial
  permutations  in  GAP  are created using the operations described in Section
  54.2. Partial permutations are, by default, displayed in component notation,
  which is described in Section 54.6.
  
  The fundamental attributes of a partial permutation are:
  
  Domain
        The  domain  of  a  partial  permutation  is  just the set of positive
        integers  where  it  is  defined; see DomainOfPartialPerm (54.3-4). We
        will denote the domain of a partial permutation f by dom(f).
  
  Degree
        The  degree  of  a  partial permutation f is just the largest positive
        integer  where  f  is  defined. In other words, the degree of f is the
        largest element in the domain of f; see DegreeOfPartialPerm (54.3-1).
  
  Image list
        The  image  list of a partial permutation f is the list [i_1^f, i_2^f,
        ..  ,  i_n^f]  where  the  domain  of  f  is  [i_1,  i_2, .., i_n] see
        ImageListOfPartialPerm (54.3-6). For example, the partial perm sending
        1 to 5 and 2 to 4 has image list [ 5, 4 ].
  
  Image set
        The  image set of a partial permutation f is just the set of points in
        the  image  list  (i.e.  the  image list after it has been sorted into
        increasing  order); see ImageSetOfPartialPerm (54.3-7). We will denote
        the image set of a partial permutation f by im(f).
  
  Codegree
        The  codegree  of a partial permutation f is just the largest positive
        integer  of the form i^f for any i in the domain of f. In other words,
        the  codegree  of  f  is  the  largest  element in the image of f; see
        CodegreeOfPartialPerm (54.3-2).
  
  Rank
        The  rank  of  a  partial  permutation f is the size of its domain, or
        equivalently   the   size   of  its  image  set  or  image  list;  see
        RankOfPartialPerm (54.3-3).
  
  A  functional  digraph is a directed graph where every vertex has out-degree
  1.  A  partial  permutation f can be thought of as a functional digraph with
  vertices  [1..DegreeOfPartialPerm(f)] and edges from i to i^f for every i. A
  component  of  a  partial  permutation  is  defined  as  a  component of the
  corresponding functional digraph. More specifically, i and j are in the same
  component  if  and only if there are i=v_0, v_1, ..., v_n=j such that either
  v_k+1=v_k^f or v_k=v_k+1^f for all k.
  
  If  S  is  a semigroup and s is an element of S, then an element t in S is a
  semigroup   inverse  for  s  if  s*t*s=s  and  t*s*t=t;  see,  for  example,
  InverseOfTransformation  (53.5-13). A semigroup in which every element has a
  unique semigroup inverse is called an inverse semigroup.
  
  Every  partial  permutation  belongs  to  a  symmetric  inverse  monoid; see
  SymmetricInverseSemigroup    (54.7-3).   Inverse   semigroups   of   partial
  permutations  are  hence  inverse  subsemigroups  of  the  symmetric inverse
  monoids.
  
  The  inverse  f^-1  of  a  partial  permutation  f  is  simply  the  partial
  permutation  that maps i^f to i for all i in the image of f. It follows that
  the  domain  of f^-1 equals the image of f and that the image of f^-1 equals
  the domain of f. The inverse f^-1 is the unique partial permutation with the
  property  that  f*f^-1*f=f and f^-1*f*f^-1=f^-1. In other words, f^-1 is the
  unique semigroup inverse of f in the symmetric inverse monoid.
  
  If  f  and  g  are  partial  permutations,  then the domain and image of the
  product are:
  
  
  dom(fg)=(im(f)\cap dom(g))f^-1 and im(fg)=(im(f)\cap dom(g))g
  
  
  
  A  partial  permutation  is  an idempotent if and only if it is the identity
  function on its domain. The products f*f^-1 and f^-1*f are just the identity
  functions on the domain and image of f, respectively. It follows that f*f^-1
  is a left identity for f and f^-1*f is a right identity. These products will
  be referred to here as the left one and right one of the partial permutation
  f;  see  LeftOne  (54.3-21).  The  one  of a partial permutation is just the
  identity on the union of its domain and its image, and the zero of a partial
  permutation  is  just  the  empty partial permutation; see One (54.3-22) and
  MultiplicativeZero (54.3-23).
  
  If  S  is  an arbitrary inverse semigroup, the natural partial order on S is
  defined  as follows: for elements x and y of S we say x≤y if there exists an
  idempotent  element  e  in S such that x=ey. In the context of the symmetric
  inverse  monoid,  a partial permutation f is less than or equal to a partial
  permutation g in the natural partial order if and only if f is a restriction
  of g. The natural partial order is a meet semilattice, in other words, every
  pair  of  elements  has  a  greatest  lower  bound;  see  MeetOfPartialPerms
  (54.2-5).
  
  Note  that  unlike permutations, partial permutations do not fix unspecified
  points  but  are simply undefined on such points; see Chapter 42. Similar to
  permutations, and unlike transformations, it is possible to multiply any two
  partial permutations in GAP.
  
  Internally,  GAP  stores a partial permutation f as a list consisting of the
  codegree of f and the images i^f of the points i that are less than or equal
  to the degree of f; the value 0 is stored where i^f is undefined. The domain
  and image set of f are also stored after either of these values is computed.
  When  the  codegree  of  a  partial  permutation  f  is less than 65536, the
  codegree  and images i^f are stored as 16-bit integers, the domain and image
  set  are  subobjects  of  f which are immutable plain lists of GAP integers.
  When  the  codegree of f is greater than or equal to 65536, the codegree and
  images are stored as 32-bit integers; the domain and image set are stored in
  the  same  way as before. A partial permutation belongs to IsPPerm2Rep if it
  is stored using 16-bit integers and to IsPPerm4Rep otherwise.
  
  In  the  names of the GAP functions that deal with partial permutations, the
  word  Permutation  is  usually  abbreviated  to  Perm,  to  save typing. For
  example,   the   category   test   function   for  partial  permutations  is
  IsPartialPerm (54.1-1).
  
  
  54.1 The family and categories of partial permutations
  
  54.1-1 IsPartialPerm
  
  IsPartialPerm( obj )  Category
  Returns:  true or false.
  
  Every  partial  permutation  in  GAP  belongs to the category IsPartialPerm.
  Basic  operations for partial permutations are DomainOfPartialPerm (54.3-4),
  ImageListOfPartialPerm     (54.3-6),     ImageSetOfPartialPerm     (54.3-7),
  RankOfPartialPerm  (54.3-3), DegreeOfPartialPerm (54.3-1), multiplication of
  two  partial  permutations  is  via  *,  and  exponentiation  with the first
  argument  a  positive  integer i and second argument a partial permutation f
  where  the  result is the image i^f of the point i under f. The inverse of a
  partial permutation f can be obtains using f^-1.
  
  54.1-2 IsPartialPermCollection
  
  IsPartialPermCollection( obj )  Category
  
  Every   collection   of   partial   permutations  belongs  to  the  category
  IsPartialPermCollection.  For  example,  a semigroup of partial permutations
  belongs in IsPartialPermCollection.
  
  54.1-3 PartialPermFamily
  
  PartialPermFamily  family
  
  The family of all partial permutations is PartialPermFamily
  
  
  54.2 Creating partial permutations
  
  There  are  several  ways of creating partial permutations in GAP, which are
  described in this section.
  
  54.2-1 PartialPerm
  
  PartialPerm( dom, img )  function
  PartialPerm( list )  function
  Returns:  A partial permutation.
  
  Partial  permutations  can  be created in two ways: by giving the domain and
  the image, or the dense image list.
  
  Domain and image
        The  partial  permutation defined by a domain dom and image img, where
        dom  is a set of positive integers and img is a duplicate free list of
        positive  integers,  maps  dom[i]  to img[i]. For example, the partial
        permutation mapping 1 and 5 to 20 and 2 can be created using:
  
          Example  
          PartialPerm([1,5],[20,2]); 
        
  
        In this setting, PartialPerm is the analogue in the context of partial
        permutations of MappingPermListList (42.5-3).
  
  Dense image list
        The  partial  permutation defined by a dense image list list, maps the
        positive  integer  i to list[i] if list[i]<>0 and is undefined at i if
        list[i]=0.  For example, the partial permutation mapping 1 and 5 to 20
        and 2 can be created using:
  
          Example  
          PartialPerm([20,0,0,0,2]);
        
  
        In this setting, PartialPerm is the analogue in the context of partial
        permutations of PermList (42.5-2).
  
  Regardless  of  which  of  these  two  methods  are used to create a partial
  permutation in GAP the internal representation is the same.
  
  If  the  largest  point in the domain is larger than the rank of the partial
  permutation,  then  using  the  dense  image  list  to  define  the  partial
  permutation  will  require  less  typing; otherwise using the domain and the
  image will require less typing. For example, the partial permutation mapping
  10000 to 1 can be defined using:
  
    Example  
    PartialPerm([10000], [1]);
  
  
  but  using the dense image list would require a list with 9999 entries equal
  to  0  and  the  final  entry equal to 1. On the other hand, the identity on
  [1,2,3,4,6] can be defined using:
  
    Example  
    PartialPerm([1,2,3,4,0,6]);
  
  
  Please  note that a partial permutation in GAP is never a permutation nor is
  a  permutation  ever  a  partial  permutation.  For example, the permutation
  (1,4,2)  fixes  3 but the partial permutation PartialPerm([4,1,0,2]); is not
  defined on 3.
  
  54.2-2 PartialPermOp
  
  PartialPermOp( obj, list[, func] )  operation
  PartialPermOpNC( obj, list[, func] )  operation
  Returns:  A partial permutation or fail.
  
  PartialPermOp returns the partial permutation that corresponds to the action
  of  the  object obj on the domain or list list via the function func. If the
  optional  third  argument  func  is  not specified, then the action OnPoints
  (41.2-1)  is  used  by  default.  Note that the returned partial permutation
  refers to the positions in list even if list itself consists of integers.
  
  This  function  is  the  analogue  in the context of partial permutations of
  Permutation (41.9-1) or TransformationOp (53.2-5).
  
  If obj does not map the elements of list injectively, then fail is returned.
  
  PartialPermOpNC does not check that obj maps elements of list injectively or
  that a partial permutation is defined by the action of obj on list via func.
  This  function  should  be used only with caution, in situations where it is
  guaranteed that the arguments have the required properties.
  
    Example  
    gap> f:=Transformation( [ 9, 10, 4, 2, 10, 5, 9, 10, 9, 6 ] );;
    gap> PartialPermOp(f, [ 6 .. 8 ], OnPoints);
    [1,4][2,5][3,6]
  
  
  54.2-3 RestrictedPartialPerm
  
  RestrictedPartialPerm( f, set )  operation
  Returns:  A partial permutation.
  
  RestrictedPartialPerm  returns  a  new  partial permutation that acts on the
  points  in  the  set of positive integers set in the same way as the partial
  permutation f, and that is undefined on those points that are not in set.
  
    Example  
    gap> f:=PartialPerm( [ 1, 3, 4, 7, 8, 9 ], [ 9, 4, 1, 6, 2, 8 ] );;
    gap> RestrictedPartialPerm(f, [ 2, 3, 6, 10 ] );
    [3,4]
  
  
  54.2-4 JoinOfPartialPerms
  
  JoinOfPartialPerms( arg )  function
  JoinOfIdempotentPartialPermsNC( arg )  function
  Returns:  A partial permutation or fail.
  
  The join of partial permutations f and g is just the join, or supremum, of f
  and g under the natural partial ordering of partial permutations.
  
  JoinOfPartialPerms  returns  the  union  of  the partial permutations in its
  argument  if  this defines a partial permutation, and fail if it is not. The
  argument  arg can be a partial permutation collection or a number of partial
  permutations.
  
  The function JoinOfIdempotentPartialPermsNC returns the join of its argument
  which  is assumed to be a collection of idempotent partial permutations or a
  number  of  idempotent  partial  permutations.  It  is  not checked that the
  arguments  are  idempotents. The performance of this function is higher than
  JoinOfPartialPerms  when  it is known a priori that the argument consists of
  idempotents.
  
  The  union  of f and g is a partial permutation if and only if f and g agree
  on  the  intersection  dom(f)∩  dom(g)  of  their  domains and the images of
  dom(f)∖ dom(g) and dom(g)∖ dom(f) under f and g, respectively, are disjoint.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );
    [3,7][8,1,2,6,9][10,5]
    gap> g:=PartialPerm( [ 11, 12, 14, 16, 18, 19 ], 
    > [ 17, 20, 11, 19, 14, 12 ] );
    [16,19,12,20][18,14,11,17]
    gap> JoinOfPartialPerms(f, g);
    [3,7][8,1,2,6,9][10,5][16,19,12,20][18,14,11,17]
    gap> f:=PartialPerm( [ 1, 4, 5, 6, 7 ], [ 5, 7, 3, 1, 4 ] );
    [6,1,5,3](4,7)
    gap> g:=PartialPerm( [ 100 ], [ 1 ] );
    [100,1]
    gap> JoinOfPartialPerms(f, g);
    fail
    gap> f:=PartialPerm( [ 1, 3, 4 ], [ 3, 2, 4 ] );
    [1,3,2](4)
    gap> g:=PartialPerm( [ 1, 2, 4 ], [ 2, 3, 4 ] );
    [1,2,3](4)
    gap> JoinOfPartialPerms(f, g);
    fail
    gap> f:=PartialPerm( [ 1 ], [ 2 ] ); 
    [1,2]
    gap> JoinOfPartialPerms(f, f^-1);
    (1,2)
  
  
  54.2-5 MeetOfPartialPerms
  
  MeetOfPartialPerms( arg )  function
  Returns:  A partial permutation.
  
  The  meet of partial permutations f and g is just the meet, or infimum, of f
  and  g  under the natural partial ordering of partial permutations. In other
  words, the meet is the greatest partial permuation which is a restriction of
  both f and g.
  
  Note that unlike the join of partial permutations, the meet always exists.
  
  MeetOfPartialPerms  returns  the  meet  of  the  partial permutations in its
  argument.  The  argument  arg  can  be a partial permutation collection or a
  number of partial permutations.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 6, 100000 ], [ 2, 6, 7, 1, 5 ] );
    [3,7][100000,5](1,2,6)
    gap> g:=PartialPerm( [ 1, 2, 3, 4, 6 ], [ 2, 4, 6, 1, 5 ] );
    [3,6,5](1,2,4)
    gap> MeetOfPartialPerms(f, g);
    [1,2]
    gap> g:=PartialPerm( [ 1, 2, 3, 5, 6, 7, 9, 10 ], 
    > [ 4, 10, 5, 6, 7, 1, 3, 2 ] );
    [9,3,5,6,7,1,4](2,10)
    gap> MeetOfPartialPerms(f, g);
    <empty partial perm>
  
  
  54.2-6 EmptyPartialPerm
  
  EmptyPartialPerm(  )  function
  Returns:  The empty partial permutation.
  
  The empty partial permutation is returned by this function when it is called
  with no arguments. This is just short hand for PartialPerm([]);.
  
    Example  
    gap> EmptyPartialPerm();
    <empty partial perm>
  
  
  
  54.2-7 RandomPartialPerm
  
  RandomPartialPerm( n )  function
  RandomPartialPerm( set )  function
  RandomPartialPerm( dom, img )  function
  Returns:  A random partial permutation.
  
  In  its  first  form,  RandomPartialPerm  returns  a randomly chosen partial
  permutation  where  points  in the domain and image are bounded above by the
  positive integer n.
  
    Example  
    gap> RandomPartialPerm(10);  
    [2,9][4,1,6,5][7,3](8)
  
  
  In  its  second  form,  RandomPartialPerm  returns a randomly chosen partial
  permutation  with  points  in  the  domain and image contained in the set of
  positive integers set.
  
    Example  
    gap> RandomPartialPerm([1,2,3,1000]);
    [2,3,1000](1)
  
  
  In  its  third  form,  RandomPartialPerm  creates  a randomly chosen partial
  permutation  with  domain  contained in the set of positive integers dom and
  image  contained  in the set of positive integers img. The arguments dom and
  img do not have to have equal length.
  
  Note  that  it  is  not  guarenteed  in  either  of these cases that partial
  permutations are chosen with a uniform distribution.
  
  
  54.3 Attributes for partial permutations
  
  In  this  section  we  describe  the  functions available in GAP for finding
  various attributes of partial permutations.
  
  54.3-1 DegreeOfPartialPerm
  
  DegreeOfPartialPerm( f )  function
  DegreeOfPartialPermCollection( coll )  attribute
  Returns:  A non-negative integer.
  
  The  degree of a partial permutation f is the largest positive integer where
  it is defined, i.e. the maximum element in the domain of f.
  
  The  degree  a collection of partial permutations coll is the largest degree
  of any partial permutation in coll.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );
    [3,7][8,1,2,6,9][10,5]
    gap> DegreeOfPartialPerm(f);
    10
  
  
  54.3-2 CodegreeOfPartialPerm
  
  CodegreeOfPartialPerm( f )  function
  CodegreeOfPartialPermCollection( coll )  attribute
  Returns:  A non-negative integer.
  
  The  codegree  of a partial permutation f is the largest positive integer in
  its image.
  
  The  codegree  a  collection  of  partial  permutations  coll is the largest
  codegree of any partial permutation in coll.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], [ 7, 1, 4, 3, 2, 6, 5 ] );
    [8,6][10,5,2,1,7](3,4)
    gap> CodegreeOfPartialPerm(f);
    7
  
  
  54.3-3 RankOfPartialPerm
  
  RankOfPartialPerm( f )  function
  RankOfPartialPermCollection( coll )  attribute
  Returns:  A non-negative integer.
  
  The  rank  of  a  partial  permutation  f  is  the  size  of  its domain, or
  equivalently the size of its image set or image list.
  
  The  rank  of a partial permutation collection coll is the size of the union
  of the domains of the elements of coll, or equivalently, the total number of
  points  on  which  the elements of coll act. Note that this is value may not
  the same as the size of the union of the images of the elements in coll.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 4, 6, 8, 9 ], [ 7, 10, 1, 9, 4, 2 ] );
    [6,9,2,10][8,4,1,7]
    gap> RankOfPartialPerm(f);
    6
  
  
  54.3-4 DomainOfPartialPerm
  
  DomainOfPartialPerm( f )  attribute
  DomainOfPartialPermCollection( f )  attribute
  Returns:  A set of positive integers (maybe empty).
  
  The  domain of a partial permutation f is the set of positive integers where
  f is defined.
  
  The  domain  of  a  partial  permutation collection coll is the union of the
  domains of its elements.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );
    [3,7][8,1,2,6,9][10,5]
    gap> DomainOfPartialPerm(f);
    [ 1, 2, 3, 6, 8, 10 ]
  
  
  54.3-5 ImageOfPartialPermCollection
  
  ImageOfPartialPermCollection( coll )  attribute
  Returns:  A set of positive integers (maybe empty).
  
  The  image  of  a  partial  permutation  collection coll is the union of the
  images of its elements.
  
    Example  
    gap> S := SymmetricInverseSemigroup(5);                                
    <symmetric inverse monoid of degree 5>
    gap> ImageOfPartialPermCollection(GeneratorsOfInverseSemigroup(S));
    [ 1 .. 5 ]
  
  
  54.3-6 ImageListOfPartialPerm
  
  ImageListOfPartialPerm( f )  attribute
  Returns:  The list of images of a partial permutation.
  
  The  image  list  of  a  partial  permutation f is the list of images of the
  elements           of          the          domain          f          where
  ImageListOfPartialPerm(f)[i]=DomainOfPartialPerm(f)[i]^f  for  any  i in the
  range from 1 to the rank of f.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], [ 7, 1, 4, 3, 2, 6, 5 ] );
    [8,6][10,5,2,1,7](3,4)
    gap> ImageListOfPartialPerm(f);
    [ 7, 1, 4, 3, 2, 6, 5 ]
  
  
  54.3-7 ImageSetOfPartialPerm
  
  ImageSetOfPartialPerm( f )  attribute
  Returns:  The image set of a partial permutation.
  
  The  image  set  of a partial permutation f is just the set of points in the
  image  list  (i.e.  the  image list after it has been sorted into increasing
  order).
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 5, 7, 10 ], [ 10, 2, 3, 5, 7, 6 ] );
    [1,10,6](2)(3)(5)(7)
    gap> ImageSetOfPartialPerm(f);
    [ 2, 3, 5, 6, 7, 10 ]
  
  
  54.3-8 FixedPointsOfPartialPerm
  
  FixedPointsOfPartialPerm( f )  attribute
  FixedPointsOfPartialPerm( coll )  method
  Returns:  A set of positive integers.
  
  FixedPointsOfPartialPerm  returns  the  set of points i in the domain of the
  partial permutation f such that i^f=i.
  
  When   the   argument   is   a  collection  of  partial  permutations  coll,
  FixedPointsOfPartialPerm returns the set of points fixed by every element of
  the collection of partial permutations coll.
  
    Example  
    gap> f := PartialPerm( [ 1, 2, 3, 6, 7 ], [ 1, 3, 4, 7, 5 ] );
    [2,3,4][6,7,5](1)
    gap> FixedPointsOfPartialPerm(f);
    [ 1 ]
    gap> f := PartialPerm([1 .. 10]);;
    gap> FixedPointsOfPartialPerm(f);
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
  
  
  54.3-9 MovedPoints
  
  MovedPoints( f )  attribute
  MovedPoints( coll )  method
  Returns:  A set of positive integers.
  
  MovedPoints  returns  the  set  of  points  i  in  the domain of the partial
  permutation f such that i^f<>i.
  
  When  the argument is a collection of partial permutations coll, MovedPoints
  returns the set of points moved by some element of the collection of partial
  permutations coll.
  
    Example  
    gap> f := PartialPerm( [ 1, 2, 3, 4 ], [ 5, 7, 1, 6 ] );
    [2,7][3,1,5][4,6]
    gap> MovedPoints(f);
    [ 1, 2, 3, 4 ]
    gap> FixedPointsOfPartialPerm(f);
    [  ]
    gap> FixedPointsOfPartialPerm(PartialPerm([1 .. 4]));
    [ 1, 2, 3, 4 ]
  
  
  54.3-10 NrFixedPoints
  
  NrFixedPoints( f )  attribute
  NrFixedPoints( coll )  method
  Returns:  A positive integer.
  
  NrFixedPoints  returns  the  number of points i in the domain of the partial
  permutation f such that i^f=i.
  
  When   the   argument   is   a  collection  of  partial  permutations  coll,
  NrFixedPoints  returns  the  number  of points fixed by every element of the
  collection of partial permutations coll.
  
    Example  
    gap> f := PartialPerm( [ 1, 2, 3, 4, 5 ], [ 3, 2, 4, 6, 1 ] );
    [5,1,3,4,6](2)
    gap> NrFixedPoints(f);
    1
    gap> NrFixedPoints(PartialPerm([1 .. 10]));
    10
  
  
  54.3-11 NrMovedPoints
  
  NrMovedPoints( f )  attribute
  NrMovedPoints( coll )  method
  Returns:  A positive integer.
  
  NrMovedPoints  returns  the  number of points i in the domain of the partial
  permutation f such that i^f<>i.
  
  When   the   argument   is   a  collection  of  partial  permutations  coll,
  NrMovedPoints  returns  the  number  of  points moved by some element of the
  collection of partial permutations coll.
  
    Example  
    gap> f := PartialPerm( [ 1, 2, 3, 4, 5, 7, 8 ], [ 4, 5, 6, 7, 1, 3, 2 ] );
    [8,2,5,1,4,7,3,6]
    gap> NrMovedPoints(f);
    7
    gap> NrMovedPoints(PartialPerm([1 .. 4]));
    0
  
  
  54.3-12 SmallestMovedPoint
  
  SmallestMovedPoint( f )  attribute
  SmallestMovedPoint( coll )  method
  Returns:  A positive integer or infinity.
  
  SmallestMovedPoint  returns the smallest positive integer i such that i^f<>i
  if  such an i exists. If f is an identity partial permutation, then infinity
  is returned.
  
  If  the  argument  is  a  collection  of partial permutations coll, then the
  smallest  point  which is moved by at least one element of coll is returned,
  if such a point exists. If coll only contains identity partial permutations,
  then SmallestMovedPoint returns infinity.
  
    Example  
    gap> f := PartialPerm( [ 1, 3 ], [ 4, 3 ] );
    [1,4](3)
    gap> SmallestMovedPoint(f);
    1
    gap> SmallestMovedPoint(PartialPerm([1 .. 10]));
    infinity
  
  
  54.3-13 LargestMovedPoint
  
  LargestMovedPoint( f )  attribute
  LargestMovedPoint( coll )  method
  Returns:  A positive integer or infinity.
  
  LargestMovedPoint  returns  the largest positive integers i such that i^f<>i
  if  such  an  i  exists. If f is the identity partial permutation, then 0 is
  returned.
  
  If  the  argument  is  a  collection  of partial permutations coll, then the
  largest point which is moved by at least one element of coll is returned, if
  such  a  point  exists. If coll only contains identity partial permutations,
  then LargestMovedPoint returns 0.
  
    Example  
    gap> f := PartialPerm( [ 1, 3, 4, 5 ], [ 5, 1, 6, 4 ] );
    [3,1,5,4,6]
    gap> LargestMovedPoint(f);
    5
    gap> LargestMovedPoint(PartialPerm([1 .. 10]));
    0
  
  
  54.3-14 SmallestImageOfMovedPoint
  
  SmallestImageOfMovedPoint( f )  attribute
  SmallestImageOfMovedPoint( coll )  method
  Returns:  A positive integer or infinity.
  
  SmallestImageOfMovedPoint  returns  the  smallest  positive integer i^f such
  that  i^f<>i  if such an i exists. If f is the identity partial permutation,
  then infinity is returned.
  
  If  the  argument  is  a  collection  of partial permutations coll, then the
  smallest integer which is the image a point moved by at least one element of
  coll  is  returned,  if  such a point exists. If coll only contains identity
  partial permutations, then SmallestImageOfMovedPoint returns infinity.
  
    Example  
    gap> S := SymmetricInverseSemigroup(5);
    <symmetric inverse monoid of degree 5>
    gap> SmallestImageOfMovedPoint(S);
    1
    gap> S := Semigroup(PartialPerm([10 .. 100], [10 .. 100]));;
    gap> SmallestImageOfMovedPoint(S);
    infinity
    gap> f := PartialPerm( [ 1, 2, 3, 6 ] );
    [4,6](1)(2)(3)
    gap> SmallestImageOfMovedPoint(f);
    6
  
  
  54.3-15 LargestImageOfMovedPoint
  
  LargestImageOfMovedPoint( f )  attribute
  LargestImageOfMovedPoint( coll )  method
  Returns:  A positive integer.
  
  LargestImageOfMovedPoint  returns the largest positive integer i^f such that
  i^f<>i  if such an i exists. If f is an identity partial permutation, then 0
  is returned.
  
  If  the  argument  is  a  collection  of partial permutations coll, then the
  largest  integer which is the image of a point moved by at least one element
  of  coll is returned, if such a point exists. If coll only contains identity
  partial permutations, then LargestImageOfMovedPoint returns 0.
  
    Example  
    gap> S := SymmetricInverseSemigroup(5);
    <symmetric inverse monoid of degree 5>
    gap> LargestImageOfMovedPoint(S);
    5
    gap> S := Semigroup(PartialPerm([10 .. 100], [10 .. 100]));;
    gap> LargestImageOfMovedPoint(S);
    0
    gap> f := PartialPerm( [ 1, 2, 3, 6 ] );;
    gap> LargestImageOfMovedPoint(f);
    6
  
  
  54.3-16 IndexPeriodOfPartialPerm
  
  IndexPeriodOfPartialPerm( f )  attribute
  Returns:  A pair of positive integers.
  
  Returns  the  least  positive integers m, r such that f^(m+r)=f^m, which are
  known as the index and period of the partial permutation f.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19 ], 
    > [ 9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1 ] );
    [2,18][3,20][6,5,11,19,1,9][7,16,13][12,14](8)
    gap> IndexPeriodOfPartialPerm(f);
    [ 6, 1 ]
    gap> f^6=f^7;
    true
  
  
  54.3-17 SmallestIdempotentPower
  
  SmallestIdempotentPower( f )  attribute
  Returns:  A positive integer.
  
  This  function  returns  the  least positive integer n such that the partial
  permutation  f^n is an idempotent. The smallest idempotent power of f is the
  least multiple of the period of f that is greater than or equal to the index
  of f; see IndexPeriodOfPartialPerm (54.3-16).
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 18, 19, 20 ], 
    > [ 5, 1, 7, 3, 10, 2, 12, 14, 11, 16, 6, 9, 15 ] );
    [4,3,7,2,1,5,10,14][8,12][13,16][18,6][19,9][20,15](11)
    gap> SmallestIdempotentPower(f);
    8
    gap> f^8;
    <identity partial perm on [ 11 ]>
  
  
  54.3-18 ComponentsOfPartialPerm
  
  ComponentsOfPartialPerm( f )  attribute
  Returns:  A list of lists of positive integer.
  
  ComponentsOfPartialPerm  returns  a  list  of  the components of the partial
  permutation  f. Each component is a subset of the domain of f, and the union
  of the components equals the domain.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], 
    > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] );
    [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17]
    gap> ComponentsOfPartialPerm(f);
    [ [ 1, 20 ], [ 2, 4, 19, 13, 15 ], [ 7, 14 ], [ 8, 3, 6 ], 
      [ 10, 12, 5, 9 ], [ 11, 17 ] ]
  
  
  54.3-19 NrComponentsOfPartialPerm
  
  NrComponentsOfPartialPerm( f )  attribute
  Returns:  A positive integer.
  
  NrComponentsOfPartialPerm  returns  the  number of components of the partial
  permutation f on its domain.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], 
    > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] );
    [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17]
    gap> NrComponentsOfPartialPerm(f);
    6
  
  
  54.3-20 ComponentRepsOfPartialPerm
  
  ComponentRepsOfPartialPerm( f )  attribute
  Returns:  A list of positive integers.
  
  ComponentRepsOfPartialPerm  returns  the  representatives,  in the following
  sense,  of the components of the partial permutation f. Every component of f
  contains a unique element in the domain but not the image of f; this element
  is called the representative of the component. If i is a representative of a
  component  of f, then for every jnot=i in the component of i, there exists a
  positive  integer k such that i ^ (f ^ k) = j. Unlike transformations, there
  is    exactly    one    representative    for    every   component   of   f.
  ComponentRepsOfPartialPerm returns the least number of representatives.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 19 ], 
    > [ 20, 4, 6, 19, 9, 14, 3, 12, 17, 5, 15, 13 ] );
    [1,20][2,4,19,13,15][7,14][8,3,6][10,12,5,9][11,17]
    gap> ComponentRepsOfPartialPerm(f);
    [ 1, 2, 7, 8, 10, 11 ]
  
  
  54.3-21 LeftOne
  
  LeftOne( f )  attribute
  RightOne( f )  attribute
  Returns:  A partial permutation.
  
  LeftOne  returns the identity partial permutation e such that the domain and
  image  of  e  equal  the  domain  of the partial permutation f and such that
  e*f=f.
  
  RightOne returns the identity partial permutation e such that the domain and
  image of e equal the image of f and such that f*e=f.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7 ], [ 10, 1, 6, 5, 8, 7 ] ); 
    [2,1,10][4,6,8](5)(7)
    gap> RightOne(f);
    <identity partial perm on [ 1, 5, 6, 7, 8, 10 ]>
    gap> LeftOne(f);
    <identity partial perm on [ 1, 2, 4, 5, 6, 7 ]>
  
  
  54.3-22 One
  
  One( f )  method
  Returns:  A partial permutation.
  
  As  described  in  OneImmutable  (31.10-2),  One  returns the multiplicative
  neutral  element of the partial permutation f, which is the identity partial
  permutation on the union of the domain and image of f. Equivalently, the one
  of f is the join of the right one and left one of f.
  
    Example  
    gap> f:=PartialPerm([ 1, 2, 3, 4, 5, 7, 10 ], [ 3, 7, 9, 6, 1, 10, 2 ]);;
    gap> One(f);
    <identity partial perm on [ 1, 2, 3, 4, 5, 6, 7, 9, 10 ]>
  
  
  54.3-23 MultiplicativeZero
  
  MultiplicativeZero( f )  method
  Returns:  The empty partial permutation.
  
  As   described   in   MultiplicativeZero   (35.4-11),   Zero   returns   the
  multiplicative zero element of the partial permutation f, which is the empty
  partial permutation.
  
    Example  
    gap> f := PartialPerm([ 1, 2, 3, 4, 5, 7, 10 ], [ 3, 7, 9, 6, 1, 10, 2 ]);;
    gap> MultiplicativeZero(f);
    <empty partial perm>
  
  
  
  54.4 Changing the representation of a partial permutation
  
  It is possible that a partial permutation in GAP can be represented by other
  types  of  objects, or that other types of GAP objects can be represented by
  partial   permutations.   Partial   permutations  which  are  mathematically
  permutations  can  be  converted into permutations in GAP using the function
  AsPermutation  (42.5-6).  Similarly,  a partial permutation can be converted
  into a transformation using AsTransformation (53.3-1).
  
  In  this section we describe functions for converting other types of objects
  in GAP into partial permutations.
  
  54.4-1 AsPartialPerm
  
  AsPartialPerm( f, set )  operation
  AsPartialPerm( f )  method
  AsPartialPerm( f, n )  method
  Returns:  A partial permutation.
  
  A  permutation  f defines a partial permutation when it is restricted to any
  finite  set  of  positive integers. AsPartialPerm can be used to obtain this
  partial permutation.
  
  There are several possible arguments for AsPartialPerm:
  
  for a permutation and set of positive integers
        AsPartialPerm returns the partial permutation that equals f on the set
        of positive integers set and that is undefined on every other positive
        integer.
  
        Note  that as explained in PartialPerm (54.2-1) a permutation is never
        a  partial  permutation  in  GAP,  please keep this in mind when using
        AsPartialPerm.
  
  for a permutation
        AsPartialPerm  returns  the  partial permutation that agrees with f on
        [1..LargestMovedPoint(f)]  and  that  is  not  defined  on  any  other
        positive integer.
  
  for a permutation and a positive integer
        AsPartialPerm  returns  the  partial permutation that agrees with f on
        [1..n],  when  n is a positive integer, and that is not defined on any
        other positive integer.
  
  The   operation   PartialPermOp   (54.2-2)  can  also  be  used  to  convert
  permutations into partial permutations.
  
    Example  
    gap> f:=(2,8,19,9,14,10,20,17,4,13,12,3,5,7,18,16);;
    gap> AsPartialPerm(f);
    (1)(2,8,19,9,14,10,20,17,4,13,12,3,5,7,18,16)(6)(11)(15)
    gap> AsPartialPerm(f, [ 1, 2, 3 ] );
    [2,8][3,5](1)
  
  
  54.4-2 AsPartialPerm
  
  AsPartialPerm( f, set )  operation
  AsPartialPerm( f, n )  method
  Returns:  A partial permutation or fail.
  
  A  transformation f defines a partial permutation when it is restricted to a
  set of positive integers where it is injective. AsPartialPerm can be used to
  obtain this partial permutation.
  
  There are several possible arguments for AsPartialPerm:
  
  for a transformation and set of positive integers
        AsPartialPerm  returns the partial permutation obtained by restricting
        f to the set of positive integers set when:
  
            set contains no elements exceeding the degree of f;
  
            f is injective on set.
  
  for a transformation and a positive integer
        AsPartialPerm  returns  the  partial permutation that agrees with f on
        [1..n]  when  A  is  a  positive  integer  and  this set satisfies the
        conditions given above.
  
  The   operation   PartialPermOp   (54.2-2)  can  also  be  used  to  convert
  transformations into partial permutations.
  
    Example  
    gap> f:=Transformation( [ 8, 3, 5, 9, 6, 2, 9, 7, 9 ] );;
    gap> AsPartialPerm(f, [1, 2, 3, 5, 8]);
    [1,8,7][2,3,5,6]
    gap> AsPartialPerm(f, 3);
    [1,8][2,3,5]
    gap> AsPartialPerm(f, [ 2 .. 4 ] );
    [2,3,5][4,9]
  
  
  
  54.5 Operators and operations for partial permutations
  
  54.5-1 Inverse
  
  Inverse( f )  method
  
  returns the inverse of the partial permutation f.
  
  54.5-2 \^
  
  \^( i, f )  method
  
  returns  the image of the positive integer i under the partial permutation f
  if it is defined and 0 if it is not.
  
  54.5-3 \/
  
  \/( i, f )  method
  
  returns the preimage of the positive integer i under the partial permutation
  f  if  it  is  defined and 0 if it is not. Note that the inverse of f is not
  calculated to find the preimage of i.
  
  54.5-4 \^
  
  \^( f, g )  method
  
  f  ^  g  returns  g^-1*f*g  when  f  is  a  partial  permutation  and g is a
  permutation  or  partial  permutation;  see  \^  (31.12-1).  This  operation
  requires  essentially  the  same  number  of  steps  as  multiplying partial
  permutations, which is around one third as many as inverting and multiplying
  twice.
  
  54.5-5 \*
  
  \*( f, g )  method
  
  f  *  g  returns  the  composition  of  f  and  g  when  f and g are partial
  permutations  or  permutations.  The  product of a permutation and a partial
  permutation is returned as a partial permutation.
  
  54.5-6 \/
  
  \/( f, g )  method
  
  f  / g returns f*g^-1 when f is a partial permutation and g is a permutation
  or  partial permutation. This operation requires essentially the same number
  of  steps  as  multiplying partial permutations, which is approximately half
  that required to first invert g and then take the product with f.
  
  54.5-7 LeftQuotient
  
  LeftQuotient( g, f )  method
  
  returns  g^-1*f  when  f  is a partial permutation and g is a permutation or
  partial  permutation. This operation requires essentially the same number of
  steps  as multiplying partial permutations, which is approximately half that
  required to first invert g and then take the product with f.
  
  54.5-8 \<
  
  \<( f, g )  method
  
  f  < g returns true if the image of f on the range from 1 to the degree of f
  is lexicographically less than the corresponding image for g and false if it
  is  not.  See  NaturalLeqPartialPerm  (54.5-13)  and  ShortLexLeqPartialPerm
  (54.5-14) for additional orders for partial permutations.
  
  54.5-9 \=
  
  \=( f, g )  method
  
  f  =  g  returns  true  if  the  partial  permutation  f  equals the partial
  permutation g and returns false if it does not.
  
  54.5-10 PermLeftQuoPartialPerm
  
  PermLeftQuoPartialPerm( f, g )  operation
  PermLeftQuoPartialPermNC( f, g )  operation
  Returns:  A permutation.
  
  Returns  the  permutation  on  the image set of f induced by f^-1*g when the
  partial permutations f and g have equal domain and image set.
  
  PermLeftQuoPartialPerm  verifies  that  f and g have equal domains and image
  sets,  and returns an error if they do not. PermLeftQuoPartialPermNC does no
  checks.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 7 ], [ 7, 9, 10, 4, 2, 5 ] );
    [1,7,5,2,9][3,10](4)
    gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 7 ], [ 7, 4, 9, 2, 5, 10 ] );
    [1,7,10][3,9](2,4)(5)
    gap> PermLeftQuoPartialPerm(f, g);
    (2,5,10,9,4)
  
  
  54.5-11 PreImagePartialPerm
  
  PreImagePartialPerm( f, i )  operation
  Returns:  A positive integer or fail.
  
  PreImagePartialPerm returns the preimage of the positive integer i under the
  partial  permutation  f if i belongs to the image of f. If i does not belong
  to the image of f, then fail is returned.
  
  The same result can be obtained by using i/f as described in Section 54.5.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 5, 9, 10 ], [ 5, 10, 7, 8, 9, 1 ] );
    [2,10,1,5,8][3,7](9)
    gap> PreImagePartialPerm(f, 8);
    5
    gap> PreImagePartialPerm(f, 5);
    1
    gap> PreImagePartialPerm(f, 1);
    10
    gap> PreImagePartialPerm(f, 10);
    2
    gap> PreImagePartialPerm(f, 2); 
    fail
  
  
  54.5-12 ComponentPartialPermInt
  
  ComponentPartialPermInt( f, i )  operation
  Returns:  A set of positive integers.
  
  ComponentPartialPermInt   returns   the  elements  of  the  component  of  f
  containing i that can be obtained by repeatedly applying f to i.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7, 8, 10, 14, 15, 16, 17, 18 ], 
    > [ 11, 4, 14, 16, 15, 3, 20, 8, 17, 19, 1, 6, 12 ] );
    [2,4,14,17,6,15,19][5,16,1,11][7,3][10,8,20][18,12]
    gap> ComponentPartialPermInt(f, 4);
    [ 4, 14, 17, 6, 15, 19 ]
    gap> ComponentPartialPermInt(f, 3);
    [  ]
    gap> ComponentPartialPermInt(f, 10);
    [ 10, 8, 20 ]
    gap> ComponentPartialPermInt(f, 100);
    [  ]
  
  
  54.5-13 NaturalLeqPartialPerm
  
  NaturalLeqPartialPerm( f, g )  function
  Returns:  true or false.
  
  The  natural  partial order ≤ on an inverse semigroup S is defined by s≤t if
  there  exists  an  idempotent  e  in  S such that s=et. Hence if f and g are
  partial  permutations,  then f≤g if and only if f is a restriction of g; see
  RestrictedPartialPerm (54.2-3).
  
  NaturalLeqPartialPerm  returns  true if f is a restriction of g and false if
  it is not. Note that since this is a partial order and not a total order, it
  is  possible  that  f  and  g  are  incomparable with respect to the natural
  partial order.
  
    Example  
    gap> f:=PartialPerm( 
    > [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], 
    > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] );;
    gap> g:=RestrictedPartialPerm(f, [ 1, 2, 3, 9, 13, 20 ] );
    [1,3,14][2,12]
    gap> NaturalLeqPartialPerm(g,f);
    true
    gap> NaturalLeqPartialPerm(f,g);
    false
    gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], 
    > [ 7, 1, 4, 3, 2, 6, 5 ] );;
    gap> NaturalLeqPartialPerm(f, g);
    false
    gap> NaturalLeqPartialPerm(g, f);
    false
  
  
  54.5-14 ShortLexLeqPartialPerm
  
  ShortLexLeqPartialPerm( f, g )  function
  Returns:  true or false.
  
  ShortLexLeqPartialPerm  returns  true if the concatenation of the domain and
  image list of f is short-lex less than the corresponding concatenation for g
  and false otherwise.
  
  Note  that  this  is not the natural partial order on partial permutation or
  the same as comparing f and g using \<.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2, 3, 4, 6, 7, 8, 10 ], 
    > [ 3, 8, 1, 9, 4, 10, 5, 6 ] );
    [2,8,5][7,10,6,4,9](1,3)
    gap> g:=PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ], 
    > [ 7, 1, 4, 3, 2, 6, 5 ] );
    [8,6][10,5,2,1,7](3,4)
    gap> f<g;
    true
    gap> g<f;
    false
    gap> ShortLexLeqPartialPerm(f, g);
    false
    gap> ShortLexLeqPartialPerm(g, f);
    true
    gap> NaturalLeqPartialPerm(f, g);
    false
    gap> NaturalLeqPartialPerm(g, f);
    false
  
  
  54.5-15 TrimPartialPerm
  
  TrimPartialPerm( f )  operation
  Returns:  Nothing.
  
  It can happen that the internal representation of a partial permutation uses
  more  memory than necessary. For example, by composing a partial permutation
  with  codegree  less  than  65536  with  a partial permutation with codegree
  greater  than 65535. It is possible that the resulting partial permutation f
  has  its  codegree  and  images stored as 32-bit integers, while none of its
  image  points  exceeds  65536. The purpose of this function is to change the
  internal  representation  of  such  an  f  from using 32-bit to using 16-bit
  integers.
  
  Note  that  the  partial  permutation  f is changed in-place, and nothing is
  returned by this function.
  
    Example  
    gap> f:=PartialPerm( [ 1, 2 ], [ 3, 4 ] )
    > *PartialPerm( [ 3, 5 ], [ 3, 100000 ] );
    [1,3]
    gap> IsPPerm4Rep(f);
    true
    gap> TrimPartialPerm(f); f;
    [1,3]
    gap> IsPPerm4Rep(f);
    false
  
  
  
  54.6 Displaying partial permutations
  
  It  is  possible  to  change  the way that GAP displays partial permutations
  using      the      user     preferences     PartialPermDisplayLimit     and
  NotationForPartialPerms;   see   Section  UserPreference  (3.2-3)  for  more
  information about user preferences.
  
  If  f  is  a  partial  permutation of rank r exceeding the value of the user
  preference PartialPermDisplayLimit, then f is displayed as:
  
    Example  
    <partial perm on r pts with degree m, codegree n>
  
  
  where  the  degree  and  codegree  are m and n, respectively. The idea is to
  abbreviate  the  display of partial permutations defined on many points. The
  default value for the PartialPermDisplayLimit is 100.
  
  If  the rank of f does not exceed the value of PartialPermDisplayLimit, then
  how   f   is   displayed  depends  on  the  value  of  the  user  preference
  NotationForPartialPerms  except  in  the  case  that  f is the empty partial
  permutation or an identity partial permutation.
  
  There are three possible values for NotationForPartialPerms user preference,
  which are described below.
  
  component
        Similar   to   permutations,   and   unlike  transformations,  partial
        permutations can be expressed as products of disjoint permutations and
        chains. A chain is a list c of some length n such that:
  
            c[1] is an element of the domain of f but not the image
  
            c[i]^f=c[i+1] for all i in the range from 1 to n-1.
  
            c[n] is in the image of f but not the domain.
  
        In the display, permutations are displayed as they usually are in GAP,
        except that fixed points are displayed enclosed in round brackets, and
        chains are displayed enclosed in square brackets.
  
          Example  
          gap> f := PartialPerm([ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ],
          > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ]);
          [1,3,14][16,8,2,12,15](4)(5,11)[6,18,10,9][7,17,20](19)
        
  
        This  option  is the most compact way to display a partial permutation
        and    is    the    default    value    of    the    user   preference
        NotationForPartialPerms.
  
  domainimage
        With  this  option a partial permutation f is displayed in the format:
        DomainOfPartialPerm(f)-> ImageListOfPartialPerm(f).
  
          Example  
          gap> f:=PartialPerm( [ 1, 2, 4, 5, 6, 7 ], [ 10, 1, 6, 5, 8, 7 ]);
          [ 1, 2, 4, 5, 6, 7 ] -> [ 10, 1, 6, 5, 8, 7 ]
        
  
  input
        With   this   option   a   partial  permutation  f  is  displayed  as:
        PartialPerm(DomainOfPartialPerm(f),  ImageListOfPartialPerm(f))  which
        corresponds  to  the input (of the first type described in PartialPerm
        (54.2-1)).
  
          Example  
          gap> f:=PartialPerm( [ 1, 2, 3, 5, 6, 9, 10 ], 
          > [ 4, 7, 3, 8, 2, 1, 6 ] );
          PartialPerm( [ 1, 2, 3, 5, 6, 9, 10 ], [ 4, 7, 3, 8, 2, 1, 6 ] )
        
  
    Example  
    gap> SetUserPreference("PartialPermDisplayLimit", 12);                
    gap> UserPreference("PartialPermDisplayLimit");
    12
    gap> f:=PartialPerm([1,2,3,4,5,6], [6,7,1,4,3,2]);
    [5,3,1,6,2,7](4)
    gap> f:=PartialPerm( 
    > [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], 
    > [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] );
    <partial perm on 15 pts with degree 19, codegree 20>
    gap> SetUserPreference("PartialPermDisplayLimit", 100);
    gap> f;
    [1,3,14][6,18,10,9][7,17,20][16,8,2,12,15](4)(5,11)(19)
    gap> UserPreference("NotationForPartialPerms");
    "component"
    gap> SetUserPreference("NotationForPartialPerms", "domainimage");
    gap> f;
    [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ] -> 
    [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ]
    gap> SetUserPreference("NotationForPartialPerms", "input");
    gap> f;
    PartialPerm( 
    [ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 16, 17, 18, 19 ], 
    [ 3, 12, 14, 4, 11, 18, 17, 2, 9, 5, 15, 8, 20, 10, 19 ] )
  
  
  
  54.7 Semigroups and inverse semigroups of partial permutations
  
  As  mentioned  at  the  start  of  the  chapter,  every inverse semigroup is
  isomorphic  to  a  semigroup of partial permutations, and in this section we
  describe  the  functions  in GAP specific to partial permutation semigroups.
  For more information about semigroups and inverse semigroups see Chapter 51.
  
  The  Semigroups  package  contains many additional functions and methods for
  computing with semigroups of partial permutations. In particular, Semigroups
  contains more efficient methods than those available in the GAP library (and
  in  many  cases  more  efficient  than  any  other  software)  for  creating
  semigroups  of  transformations,  calculating  their  Green's classes, size,
  elements,  group  of  units,  minimal  ideal, small generating sets, testing
  membership,  finding the inverses of a regular element, factorizing elements
  over the generators, and more.
  
  Since  a  partial  permutation  semigroup  is  also  a  partial  permutation
  collection,  there  are  special  methods  for DomainOfPartialPermCollection
  (54.3-4),  ImageOfPartialPermCollection  (54.3-5),  FixedPointsOfPartialPerm
  (54.3-8),   MovedPoints  (54.3-9),  NrFixedPoints  (54.3-10),  NrMovedPoints
  (54.3-11),  LargestMovedPoint  (54.3-13),  and  SmallestMovedPoint (54.3-12)
  when applied to a partial permutation semigroup.
  
  54.7-1 IsPartialPermSemigroup
  
  IsPartialPermSemigroup( obj )  filter
  IsPartialPermMonoid( obj )  filter
  Returns:  true or false.
  
  A  partial  perm  semigroup  is  simply  a  semigroup  consisting of partial
  permutations, which may or may not be an inverse semigroup. An object obj in
  GAP  is  a  partial  perm  semigroup if and only if it satisfies IsSemigroup
  (51.1-1) and IsPartialPermCollection (54.1-2).
  
  A  partial  perm  monoid  is a monoid consisting of partial permutations. An
  object in GAP is a partial perm monoid if it satisfies IsMonoid (51.2-1) and
  IsPartialPermCollection (54.1-2).
  
  Note   that  it  is  possible  for  a  partial  perm  semigroup  to  have  a
  multiplicative neutral element (i.e. an identity element) but not to satisfy
  IsPartialPermMonoid. For example,
  
    Example  
    gap> f := PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );;
    gap> S := Semigroup(f, One(f));
    <commutative partial perm monoid of rank 9 with 1 generator>
    gap> IsMonoid(S);
    true
    gap> IsPartialPermMonoid(S);
    true
  
  
  Note  that  unlike transformation semigroups, the One (31.10-2) of a partial
  permutation semigroup must coincide with the multiplicative neutral element,
  if either exists.
  
  For more details see IsMagmaWithOne (35.1-2).
  
  54.7-2 DegreeOfPartialPermSemigroup
  
  DegreeOfPartialPermSemigroup( S )  attribute
  CodegreeOfPartialPermSemigroup( S )  attribute
  RankOfPartialPermSemigroup( S )  attribute
  Returns:  A non-negative integer.
  
  The degree of a partial permutation semigroup S is the largest degree of any
  partial permutation in S.
  
  The  codegree  of  a partial permutation semigroup S is the largest positive
  integer in its image.
  
  The  rank  of  a  partial permutation semigroup S is the number of points on
  which it acts.
  
    Example  
    gap> S := Semigroup( PartialPerm( [ 1, 5 ], [ 10000, 3 ] ) );
    <commutative partial perm semigroup of rank 2 with 1 generator>
    gap> DegreeOfPartialPermSemigroup(S);
    5
    gap> CodegreeOfPartialPermSemigroup(S);
    10000
    gap> RankOfPartialPermSemigroup(S);
    2
  
  
  54.7-3 SymmetricInverseSemigroup
  
  SymmetricInverseSemigroup( n )  operation
  SymmetricInverseMonoid( n )  operation
  Returns:  The symmetric inverse semigroup of degree n.
  
  If  n  is a non-negative integer, then SymmetricInverseSemigroup returns the
  inverse  semigroup  consisting  of  all partial permutations with degree and
  codegree at most n. Note that n must be non-negative, but in particular, can
  equal 0.
  
  The  symmetric  inverse  semigroup  is  generated by any set that of partial
  permutations  that  generate the symmetric group on n points and any partial
  permutation of rank n-1.
  
  SymmetricInverseMonoid is a synonym for SymmetricInverseSemigroup.
  
    Example  
    gap> S := SymmetricInverseSemigroup(5);
    <symmetric inverse monoid of degree 5>
    gap> Size(S);
    1546
    gap> GeneratorsOfInverseMonoid(S);
    [ (1,2,3,4,5), (1,2)(3)(4)(5), [5,4,3,2,1] ]
  
  
  54.7-4 IsSymmetricInverseSemigroup
  
  IsSymmetricInverseSemigroup( S )  property
  IsSymmetricInverseMonoid( S )  property
  Returns:  true or false.
  
  If  the  partial  perm  semigroup  S  of  degree  and  codegree n equals the
  symmetric  inverse  semigroup  on n points, then IsSymmetricInverseSemigroup
  return true and otherwise it returns false.
  
  IsSymmetricInverseMonoid  is a synonym of IsSymmetricInverseSemigroup. It is
  common  in the literature for the symmetric inverse monoid to be referred to
  as the symmetric inverse semigroup.
  
    Example  
    gap> S := Semigroup(AsPartialPerm((1, 3, 4, 2), 5), AsPartialPerm((1, 3, 5), 5),
    > PartialPerm( [ 1, 2, 3, 4 ] ) );
    <partial perm semigroup of rank 5 with 3 generators>
    gap> IsSymmetricInverseSemigroup(S);
    true
    gap> S;
    <symmetric inverse monoid of degree 5>
  
  
  54.7-5 NaturalPartialOrder
  
  NaturalPartialOrder( S )  attribute
  ReverseNaturalPartialOrder( S )  attribute
  Returns:  The natural partial order on an inverse semigroup.
  
  The  natural  partial order ≤ on an inverse semigroup S is defined by s≤t if
  there  exists  an  idempotent  e  in  S such that s=et. Hence if f and g are
  partial  permutations,  then f≤g if and only if f is a restriction of g; see
  RestrictedPartialPerm (54.2-3).
  
  NaturalPartialOrder  returns  the  natural  partial  order  on  the  inverse
  semigroup  of  partial permutations S as a list of sets of positive integers
  where  entry  i  in  NaturalPartialOrder(S)  is  the  set  of  positions  in
  Elements(S)  of  elements  which  are  less  than  Elements(S)[i].  See also
  NaturalLeqPartialPerm (54.5-13).
  
  ReverseNaturalPartialOrder  returns the reverse of the natural partial order
  on  the  inverse  semigroup  of  partial permutations S as a list of sets of
  positive  integers where entry i in ReverseNaturalPartialOrder(S) is the set
  of   positions   in   Elements(S)   of   elements  which  are  greater  than
  Elements(S)[i]. See also NaturalLeqPartialPerm (54.5-13).
  
    Example  
    gap> S := InverseSemigroup([ PartialPerm( [ 1, 3 ], [ 1, 3 ] ),
    > PartialPerm( [ 1, 2 ], [ 3, 2 ] ) ] );
    <inverse partial perm semigroup of rank 3 with 2 generators>
    gap> Size(S);
    11
    gap> NaturalPartialOrder(S);
    [ [  ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 1 ], [ 1 ], 
      [ 1, 4, 7 ], [ 1, 4, 8 ], [ 1, 2, 8 ] ]
    gap> NaturalLeqPartialPerm(Elements(S)[4], Elements(S)[10]);
    true
    gap> NaturalLeqPartialPerm(Elements(S)[4], Elements(S)[1]); 
    false
  
  
  54.7-6 IsomorphismPartialPermSemigroup
  
  IsomorphismPartialPermSemigroup( S )  attribute
  IsomorphismPartialPermMonoid( S )  attribute
  Returns:  An isomorphism.
  
  IsomorphismPartialPermSemigroup(S)  returns  an isomorphism from the inverse
  semigroup S to an inverse semigroup of partial permutations.
  
  IsomorphismPartialPermMonoid(S)  returns  an  isomorphism  from  the inverse
  semigroup S to an inverse monoid of partial permutations, if possible.
  
  We  only describe IsomorphismPartialPermMonoid, the corresponding statements
  for IsomorphismPartialPermSemigroup also hold.
  
  Partial permutation semigroups
        If S is a partial permutation semigroup that does not satisfy IsMonoid
        (51.2-1)   but   where   MultiplicativeNeutralElement(S)<>fail,   then
        IsomorphismPartialPermMonoid(S)  returns  an  isomorphism from S to an
        inverse monoid of partial permutations.
  
  Permutation groups
        If S is a permutation group, then IsomorphismPartialPermMonoid returns
        an  isomorphism from S to an inverse monoid of partial permutations on
        the  set  MovedPoints(S)  obtained  using  AsPartialPerm (54.4-1). The
        inverse of this isomorphism is obtained using AsPermutation (42.5-6).
  
  Transformation semigroups
        If  S  is  a transformation semigroup which is mathematically a monoid
        but  which  does  not  necessarily  belong  to  the  category IsMonoid
        (51.2-1),  then  IsomorphismPartialPermMonoid  returns  an isomorphism
        from S to an inverse monoid of partial permutations.
  
    Example  
    gap> S := InverseSemigroup( 
    > PartialPerm( [ 1, 2, 3, 4, 5 ], [ 4, 2, 3, 1, 5 ] ),
    > PartialPerm( [ 1, 2, 4, 5 ], [ 3, 1, 4, 2 ] ) );;
    gap> IsMonoid(S); 
    false
    gap> Size(S);
    508
    gap> iso := IsomorphismPartialPermMonoid(S);
    MappingByFunction( <inverse partial perm semigroup of size 508, 
     rank 5 with 2 generators>, <inverse partial perm monoid of size 508, 
     rank 5 with 2 generators>
     , function( object ) ... end, function( object ) ... end )
    gap> Size(S);
    508
    gap> Size(Range(iso));
    508
    gap> G := Group((1,2)(3,8)(4,6)(5,7), (1,3,4,7)(2,5,6,8), (1,4)(2,6)(3,7)(5,8));;
    gap> IsomorphismPartialPermSemigroup(G);
    MappingByFunction( Group([ (1,2)(3,8)(4,6)(5,7), (1,3,4,7)
    (2,5,6,8), (1,4)(2,6)(3,7)
    (5,8) ]), <partial perm group of rank 8 with 3 generators>
    , function( p ) ... end, <Attribute "AsPermutation"> )
    gap> S := Semigroup(Transformation( [ 2, 5, 1, 7, 3, 7, 7 ] ), 
    > Transformation( [ 3, 6, 5, 7, 2, 1, 7 ] ) );;
    gap> iso := IsomorphismPartialPermMonoid(S);;
    gap> MultiplicativeNeutralElement(S) ^ iso;
    <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]>
    gap> One(Range(iso));
    <identity partial perm on [ 1, 2, 3, 4, 5, 6 ]>
    gap> MovedPoints(Range(iso));
    [ 1 .. 5 ]