  
  [1X3 [33X[0;0YFundamental and Combinatorial Structures and Associated Graph Algorithms[133X[101X
  
  [33X[0;0YThis  chapter  details  the [10XFundamental[110X and [10XCombinatorial[110X records, which are
  used  for  creating  and manipulating structured data representations within
  GAP.  It  also  covers functions for converting these structures into graphs
  and for computing their stabilizers and canonical forms.[133X
  
  [33X[0;0YFundamental  structures  can  be  passed directly to [2XCanonicalImage[102X ([14X2.2-5[114X),
  [2XCanonicalImagePerm[102X  ([14X2.2-5[114X)  and  [2XIsCanonicalImage[102X  ([14X2.2-5[114X), with the action
  [10XOnFundamental[110X  (which is also the default action for them). [12XNote:[112X unless the
  group  is  a  direct  product  of natural symmetric groups (such as the full
  symmetric  group  on  the  atoms),  canonicalising  a  fundamental structure
  requires  the  optional [5Xvole[105X package to be loaded. The graph computations in
  this chapter use bliss, through the required [5XDigraphs[105X package.[133X
  
  
  [1X3.1 [33X[0;0YWorked examples[133X[101X
  
  [33X[0;0YAs  a  first  example we canonicalise Latin squares, considering two squares
  equivalent  (isotopic)  if  one  can  be reached from the other by permuting
  rows, permuting columns, and renaming symbols. We represent a square as a 2D
  matrix  whose row and column indices are drawn from points disjoint from the
  symbols,  and  attach  a  colouring  so  rows, columns and symbols cannot be
  exchanged with each other.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XLoadPackage("images", false);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xn := 4;;[127X[104X
    [4X[25Xgap>[125X [27Xrow := [n+1..2*n];;  col := [2*n+1..3*n];;[127X[104X
    [4X[25Xgap>[125X [27Xenc := m -> Combinatorial.WithColoring([127X[104X
    [4X[25X>[125X [27X       Combinatorial.Matrix2D(m, row, col), [[1..n], row, col]);;[127X[104X
    [4X[25Xgap>[125X [27Xklein := [[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]];;[127X[104X
  [4X[32X[104X
  
  [33X[0;0YNow  any  group  acting  on the points [10X[1..3*n][110X can be used to canonicalise;
  permutations which mix the colour classes are excluded by the colouring. The
  canonical  image is the same whichever equivalent square we start from: here
  we  scramble  the  Klein  table  by  swapping  two symbols, two rows and two
  columns.  The  order  4 Latin squares fall into exactly two isotopy classes,
  represented  by  the Klein and cyclic group tables, and the canonical images
  separate them.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xklein2 := [[3,1,2,4],[1,3,4,2],[2,4,3,1],[4,2,1,3]];;[127X[104X
    [4X[25Xgap>[125X [27Xz4 := [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]];;[127X[104X
    [4X[25Xgap>[125X [27Xcan1 := CanonicalImage(SymmetricGroup(3*n), enc(klein), OnFundamental);;[127X[104X
    [4X[25Xgap>[125X [27Xcan2 := CanonicalImage(SymmetricGroup(3*n), enc(klein2), OnFundamental);;[127X[104X
    [4X[25Xgap>[125X [27Xcan3 := CanonicalImage(SymmetricGroup(3*n), enc(z4), OnFundamental);;[127X[104X
    [4X[25Xgap>[125X [27Xcan1 = can2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xcan1 = can3;[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAs  a second example, the multiplication table of a semigroup of order [22Xn[122X can
  be canonicalised up to isomorphism as a 2D matrix on which [10XSymmetricGroup(n)[110X
  acts simultaneously on values, rows and columns.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xmat := [[1,2,3,4],[1,4,3,2],[1,2,4,3],[4,2,1,3]];;[127X[104X
    [4X[25Xgap>[125X [27Xfullm := Combinatorial.Matrix2D(mat, [1..4], [1..4]);;[127X[104X
    [4X[25Xgap>[125X [27XCanonicalImagePerm(SymmetricGroup(4), fullm);[127X[104X
    [4X[28X(1,4,3,2)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YA   pair   of   such   tables  can  be  treated  as  an  ordered  pair  with
  [10XCombinatorial.Tuple[110X, or as an unordered pair with [10XCombinatorial.Multiset[110X.[133X
  
  
  [1X3.2 [33X[0;0YFunction documentation[133X[101X
  
  [1X3.2-1 Fundamental[101X
  
  [33X[1;0Y[29X[2XFundamental[102X [32X global variable[133X
  
  [33X[0;0YThe  [10XFundamental[110X  record provides the basic building blocks for representing
  structured  data.  These  structures  are records typically containing [10Xkind[110X,
  [10Xcontents[110X,  and [10Xtype[110X fields. It also defines constants for different kinds of
  structures.[133X
  
  [33X[0;0YThe following components are available in the [10XFundamental[110X record:[133X
  
  [8X[10XAtomOf( [3Xa[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns a new fundamental structure representing an Atom with value [3Xa[103X.[133X
  
  [8X[10XAtomOfWithType( [3Xa[103X[8X[10X, [3Xt[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a new fundamental structure representing an Atom with value [3Xa[103X
        and type [3Xt[103X.[133X
  
  [8X[10XCollectionOf( [3Xl[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a  new  fundamental  structure  representing  the  collection
        containing the list [3Xl[103X.[133X
  
  [8X[10XCollectionOfWithType( [3Xl[103X[8X[10X, [3Xt[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a  new  fundamental  structure  representing  the  collection
        containing the list [3Xl[103X, of type [3Xt[103X.[133X
  
  [8X[10XTupleOf( [3Xl[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a new fundamental structure representing the tuple containing
        the list [3Xl[103X..[133X
  
  [8X[10XTupleOfWithType( [3Xl[103X[8X[10X, [3Xt[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a new fundamental structure representing the tuple containing
        the list [3Xl[103X, of type [3Xt[103X.[133X
  
  [33X[0;0YThe   record  also  contains  the  constants  [10XAtomType[110X,  [10XCollectionType[110X  and
  [10XTupleType[110X, the possible values of the [10Xkind[110X field of a fundamental structure.[133X
  
  [33X[0;0YThe  [10XFundamental[110X  record  provides  the basic building blocks such as atoms,
  collections,  and  tuples.  Building  upon  these,  the [10XCombinatorial[110X record
  offers convenient constructors for common mathematical objects.[133X
  
  [1X3.2-2 Combinatorial[101X
  
  [33X[1;0Y[29X[2XCombinatorial[102X [32X global variable[133X
  
  [33X[0;0YThe  [10XCombinatorial[110X  record  provides  a collection of functions to construct
  various  standard  combinatorial  objects. These objects are built using the
  underlying structures defined in [2XFundamental[102X ([14X3.2-1[114X).[133X
  
  [33X[0;0YThe following components are available in the [10XCombinatorial[110X record:[133X
  
  [8X[10XAtom( [3Xa[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns   a   fundamental  atom  structure  representing  [3Xa[103X.  This  is
        equivalent to calling [10XFundamental.AtomOfWithType( [3Xa[103X[10X, "atom" )[110X.[133X
  
  [8X[10XSet( [3Xl[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns a fundamental collection structure representing a set from the
        list  [3Xl[103X.  The  elements  in  [3Xl[103X  are  typically  fundamental structures
        themselves.       This       is       equivalent       to      calling
        [10XFundamental.CollectionOfWithType( [3Xl[103X[10X, "set" )[110X.[133X
  
  [8X[10XMultiset( [3Xl[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a  fundamental  collection  structure representing a multiset
        from    the    list    [3Xl[103X.    This    is    equivalent    to    calling
        [10XFundamental.CollectionOfWithType( [3Xl[103X[10X, "multiset" )[110X.[133X
  
  [8X[10XTuple( [3Xl[103X[8X[10X )[110X[8X[108X
        [33X[0;6YReturns  a  fundamental  tuple  structure  from  the  list  [3Xl[103X. This is
        equivalent to calling [10XFundamental.TupleOfWithType( [3Xl[103X[10X, "tuple" )[110X.[133X
  
  [8X[10XMatrix( [3Xvals[103X[8X[10X, [3Xindex[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConstructs  a  1D  matrix representation. [3Xvals[103X is a list of values and
        [3Xindex[103X  is  a  list of corresponding indices. The function asserts that
        [3Xvals[103X  and  [3Xindex[103X  have the same length. The matrix is represented as a
        fundamental  collection of type [10X"matrix1dtop"[110X, where each element is a
        fundamental tuple of type [10X"matrix1d"[110X containing a pair [10X[val, idx][110X.[133X
  
  [8X[10XMatrix2D( [3Xvals[103X[8X[10X, [3Xindex1[103X[8X[10X, [3Xindex2[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConstructs  a  2D  matrix  representation.  [3Xvals[103X is a 2D list (list of
        lists)  of  values,  [3Xindex1[103X  is a list of row indices, and [3Xindex2[103X is a
        list  of  column  indices.  The  function  asserts that the dimensions
        match.  The  matrix is represented as a fundamental collection of type
        [10X"matrix2dtop"[110X,  where  each  element  is  a  fundamental tuple of type
        [10X"matrix2d"[110X containing a triplet [10X[val, idx1, idx2][110X.[133X
  
  [8X[10XPermutation( [3Xp[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConverts  a  GAP  permutation [3Xp[103X into a fundamental structure. It lists
        the  moved  points  of  [3Xp[103X as pairs [10X[point, point^p][110X. Each such pair is
        converted  into  a  fundamental  tuple of atoms. These tuples are then
        collected into a fundamental collection of type [10X"permutation"[110X.[133X
  
  [8X[10XTransformation( [3Xp[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConverts  a GAP transformation [3Xp[103X into a fundamental structure. Similar
        to  [10XPermutation[110X,  it  uses  moved  points [10X[point, point^p][110X and forms a
        fundamental collection of type [10X"transformation"[110X.[133X
  
  [8X[10XPartialPermutation( [3Xp[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConverts  a  GAP  partial  permutation [3Xp[103X into a fundamental structure.
        Similar  to  [10XPermutation[110X,  it  uses  moved points [10X[point, point^p][110X and
        forms a fundamental collection of type [10X"partialpermutation"[110X.[133X
  
  [8X[10XOrderedPartition( [3Xp[103X[8X[10X )[110X[8X[108X
        [33X[0;6YConverts  a list of lists [3Xp[103X into a fundamental tuple of collections of
        type  [10X"orderedpartition"[110X:  the  order  of the parts matters, the order
        within each part does not.[133X
  
  [8X[10XWithColoring( [3Xf[103X[8X[10X, [3Xcols[103X[8X[10X )[110X[8X[108X
        [33X[0;6YAttaches a colouring to the fundamental structure [3Xf[103X: [3Xcols[103X is a list of
        lists  of  points,  and two points may only be mapped to each other if
        they  lie  in  the  same  list.  This  is  the  way  to restrict which
        relabellings of [3Xf[103X are considered.[133X
  
  [33X[0;0YThe following functions operate on these fundamental structures:[133X
  
  [1X3.2-3 OnFundamental[101X
  
  [33X[1;0Y[29X[2XOnFundamental[102X( [3Xf[103X, [3Xp[103X ) [32X function[133X
  
  [33X[0;0YApplies a permutation [3Xp[103X to a fundamental structure [3Xf[103X or to an integer.[133X
  
  [33X[0;0YIf [3Xf[103X is an integer, it returns the image of [3Xf[103X under [3Xp[103X (i.e., [10X[3Xf[103X[10X^[3Xp[103X[10X[110X).[133X
  
  [33X[0;0YIf  [3Xf[103X  is  a  fundamental  structure (a record with [10Xkind[110X, [10Xcontents[110X, and [10Xtype[110X
  fields):[133X
  
  [30X    [33X[0;6YIf [10X[3Xf[103X[10X.kind[110X is [10XFundamental.AtomType[110X, it applies [3Xp[103X to [10X[3Xf[103X[10X.contents[110X.[133X
  
  [30X    [33X[0;6YIf   [10X[3Xf[103X[10X.kind[110X   is   [10XFundamental.CollectionType[110X,  it  recursively  calls
        [10XOnFundamental[110X  on each element of [10X[3Xf[103X[10X.contents[110X with [3Xp[103X, and the resulting
        list of contents is sorted.[133X
  
  [30X    [33X[0;6YIf [10X[3Xf[103X[10X.kind[110X is [10XFundamental.TupleType[110X, it recursively calls [10XOnFundamental[110X
        on  each  element  of  [10X[3Xf[103X[10X.contents[110X with [3Xp[103X. The order of elements in the
        tuple is preserved.[133X
  
  [33X[0;0YA  new  fundamental  structure is returned with the modified contents, while
  the  [10Xkind[110X  and  [10Xtype[110X  fields are preserved from the original structure [3Xf[103X. An
  error is raised if [3Xf[103X has an invalid [10Xkind[110X.[133X
  
  [33X[0;0YThe  action  is  also  installed  as the power operation, so [10X[3Xf[103X[10X^[3Xp[103X[10X[110X may be used
  instead.[133X
  
  [33X[0;0YThis function describes how permutations act on fundamental structures.[133X
  
  [1X3.2-4 AtomsOfFundamentalStructure[101X
  
  [33X[1;0Y[29X[2XAtomsOfFundamentalStructure[102X( [3Xf[103X ) [32X function[133X
  
  [33X[0;0YReturns  the  set of all atoms (the underlying points) occurring anywhere in
  the fundamental structure [3Xf[103X.[133X
  
  [1X3.2-5 GraphOfFundamentalStructure[101X
  
  [33X[1;0Y[29X[2XGraphOfFundamentalStructure[102X( [3Xs[103X, [3Xomega[103X, [3Xparts[103X ) [32X function[133X
  
  [33X[0;0YConstructs a graph representation of a fundamental structure [3Xs[103X.[133X
  
  [33X[0;0Y[3Xs[103X is the fundamental structure to be converted into a graph. [3Xomega[103X is a list
  of  atomic elements (often integers) that form the base points of the graph.
  These are typically the objects upon which permutations will act. [3Xparts[103X is a
  list  of lists, representing a partition of [3Xomega[103X. This partition is used to
  assign  initial  colors  to the vertices corresponding to elements of [3Xomega[103X.
  For  an  element  [10Xj[110X  in  [10X[3Xparts[103X[10X[i][110X,  its corresponding vertex is colored with
  [10X[Fundamental.PAtom,  i][110X.  Elements  of  [3Xomega[103X  not  in any list in [3Xparts[103X are
  colored with [10XFundamental.PAtom[110X.[133X
  
  [33X[0;0YThe  function  returns  a  record,  let's  call it [10Xgraph[110X, with the following
  components:[133X
  
  [8X[10Xvertices[110X[8X[108X
        [33X[0;6YA list of records, where each record represents a vertex in the graph.
        Each vertex record has at least [10Xname[110X, [10Xcolour[110X, [10Xheight[110X, and [10Xid[110X fields.[133X
  
  [8X[10Xedges[110X[8X[108X
        [33X[0;6YA  list  of  pairs  [10X[u,  v][110X,  where  [10Xu[110X  and  [10Xv[110X  are  IDs  of vertices,
        representing directed edges from [10Xu[110X to [10Xv[110X.[133X
  
  [8X[10Xomega[110X[8X[108X
        [33X[0;6YThe length of the input list [3Xomega[103X.[133X
  
  [8X[10Xatoms[110X[8X[108X
        [33X[0;6YA  hash  map where keys are the elements from [3Xomega[103X and values are the
        IDs of their corresponding vertices in [10Xgraph.vertices[110X.[133X
  
  [33X[0;0YThe  graph  construction  recursively traverses the fundamental structure [3Xs[103X,
  creating  vertices  for  atoms, collections, and tuples, and connecting them
  appropriately.   Optimizations  ([10X_IMAGES_DO_ATOM_OPT[110X,  [10X_IMAGES_DO_TUPLE_OPT[110X)
  might affect the exact structure for performance.[133X
  
  [33X[0;0YThis  function  explains  the  conversion  of a fundamental structure into a
  graph  representation, which is essential for the subsequent algorithms. The
  stabilizer  of  these  structures  can  be  computed,  either  over the full
  symmetric group or within a user-specified group:[133X
  
  [1X3.2-6 StabilizerOfFundamentalStructure[101X
  
  [33X[1;0Y[29X[2XStabilizerOfFundamentalStructure[102X( [3Xfs[103X, [3Xomega[103X[, [3Xparts[103X] ) [32X function[133X
  
  [33X[0;0YComputes  the  stabilizer group of the fundamental structure [3Xfs[103X with respect
  to a set of base points [3Xomega[103X.[133X
  
  [33X[0;0Y[3Xfs[103X  is  the  fundamental  structure.  [3Xomega[103X  is  a  list of atomic elements,
  representing  the set of points on which the resulting group will act. [3Xparts[103X
  (optional) is a partition of [3Xomega[103X, used for coloring the graph derived from
  [3Xfs[103X. If not provided, an empty partition [10X[][110X is used.[133X
  
  [33X[0;0YThe  function  first  converts  the  fundamental structure [3Xfs[103X into a digraph
  using  [10X_convertToDigraph[110X (which internally calls [2XGraphOfFundamentalStructure[102X
  ([14X3.2-5[114X)). This digraph also has an associated vertex coloring based on [3Xparts[103X
  and the types of internal nodes. Then, it computes the automorphism group of
  this colored digraph using [10XBlissAutomorphismGroup[110X from the [5XDigraphs[105X package.
  Finally, the resulting automorphism group is returned as a permutation group
  acting on the points in [3Xomega[103X.[133X
  
  [1X3.2-7 StabilizerOfFundamentalStructureWithGroup[101X
  
  [33X[1;0Y[29X[2XStabilizerOfFundamentalStructureWithGroup[102X( [3Xfs[103X, [3Xomega[103X, [3Xgrp[103X ) [32X function[133X
  
  [33X[0;0YComputes  the  stabilizer  of  the  fundamental  structure [3Xfs[103X within a given
  permutation group [3Xgrp[103X. This function requires the [5Xvole[105X package to be loaded.[133X
  
  [33X[0;0Y[3Xfs[103X  is  the fundamental structure. [3Xomega[103X is a list of atomic elements, which
  must  contain  every  atom  of  [3Xfs[103X  and  every  point moved by [3Xgrp[103X. [3Xgrp[103X is a
  permutation  group acting on the points in [3Xomega[103X. The search for stabilizing
  permutations is restricted to [3Xgrp[103X.[133X
  
  [33X[0;0YThe  function  converts  [3Xfs[103X  into a colored digraph (using [10X_convertToDigraph[110X
  with  [3Xomega[103X  as  a single part for coloring). It then constructs a candidate
  group  for  [10XVoleFind.Group[110X  by combining [3Xgrp[103X (acting on [3Xomega[103X vertices) with
  the  symmetric  group  on  the  remaining  non-[3Xomega[103X  vertices of the graph.
  [10XVoleFind.Group[110X  is  used  to  find the subgroup of this candidate group that
  stabilizes  the  digraph  and  its  coloring.  The  resulting  group is then
  restricted  to  act  only  on  the  vertices  corresponding  to [3Xomega[103X and is
  returned.[133X
  
  [33X[0;0YSimilarly, canonical permutations can be found:[133X
  
  [1X3.2-8 CanonicalPermOfFundamentalStructure[101X
  
  [33X[1;0Y[29X[2XCanonicalPermOfFundamentalStructure[102X( [3Xfs[103X, [3Xomega[103X ) [32X function[133X
  
  [33X[0;0YComputes  a canonicalizing permutation for the fundamental structure [3Xfs[103X with
  respect  to  [3Xomega[103X. This function assumes the full symmetric group is acting
  on [3Xomega[103X.[133X
  
  [33X[0;0Y[3Xfs[103X is the fundamental structure. [3Xomega[103X is a list of atomic elements.[133X
  
  [33X[0;0YThis     function     is     a     convenience     wrapper     that    calls
  [2XCanonicalPermOfFundamentalStructureWithGroup[102X  ([14X3.2-9[114X)  with  [3Xfs[103X,  [3Xomega[103X, and
  [10XSymmetricGroup([3Xomega[103X[10X)[110X. It requires the [5Xvole[105X package to be loaded. It returns
  a permutation acting on [3Xomega[103X that maps [3Xfs[103X to its canonical form.[133X
  
  [1X3.2-9 CanonicalPermOfFundamentalStructureWithGroup[101X
  
  [33X[1;0Y[29X[2XCanonicalPermOfFundamentalStructureWithGroup[102X( [3Xfs[103X, [3Xomega[103X, [3Xgrp[103X ) [32X function[133X
  
  [33X[0;0YComputes  a canonicalizing permutation for the fundamental structure [3Xfs[103X with
  respect  to  [3Xomega[103X,  restricting  the search to the group [3Xgrp[103X. This function
  requires the [5Xvole[105X package to be loaded.[133X
  
  [33X[0;0Y[3Xfs[103X  is  the fundamental structure. [3Xomega[103X is a list of atomic elements, which
  must  contain  every  atom  of  [3Xfs[103X  and  every  point moved by [3Xgrp[103X. [3Xgrp[103X is a
  permutation group acting on the points in [3Xomega[103X.[133X
  
  [33X[0;0YSimilar  to [2XStabilizerOfFundamentalStructureWithGroup[102X ([14X3.2-7[114X), this function
  converts  [3Xfs[103X  to  a colored digraph. It forms a candidate group by combining
  [3Xgrp[103X  (acting  on  [3Xomega[103X  vertices)  with  the  symmetric  group on non-[3Xomega[103X
  vertices.  [10XVoleFind.CanonicalPerm[110X  is  then  used to find a permutation from
  this candidate group that maps the digraph (and its coloring) to a canonical
  form.  The  resulting  permutation  is  restricted  to  act  on [3Xomega[103X and is
  returned.  This  permutation,  when applied to [3Xomega[103X and used to relabel [3Xfs[103X,
  would yield a canonical representation of [3Xfs[103X under the action of [3Xgrp[103X.[133X
  
  [33X[0;0YFinally,  a  utility function for refining canonical labellings with respect
  to colorings is provided:[133X
  
  [1X3.2-10 MakeCanonicalLabellingRespectColors[101X
  
  [33X[1;0Y[29X[2XMakeCanonicalLabellingRespectColors[102X( [3Xn[103X, [3Xp[103X, [3Xcolours[103X ) [32X function[133X
  
  [33X[0;0YAdjusts  a permutation [3Xp[103X (acting on [10X[1..[3Xn[103X[10X][110X) to create a new permutation that
  respects  a  given  coloring. The intent is to refine a canonical labeling [3Xp[103X
  such that elements within the same color class are ordered canonically based
  on their preimages under [3Xp[103X.[133X
  
  [33X[0;0Y[3Xn[103X  is  the  number of points being permuted; it is raised internally if [3Xp[103X or
  [3Xcolours[103X  mention larger points, and points of [10X[1..[3Xn[103X[10X][110X not in any colour class
  are  treated  as  one  extra  class. [3Xp[103X is the input permutation, typically a
  canonical labeling permutation obtained from a graph algorithm. [3Xcolours[103X is a
  list of lists, where each inner list [10X[3Xcolours[103X[10X[i][110X contains points belonging to
  the i-th color class. These inner lists are treated as sets.[133X
  
  [33X[0;0YThe function works as follows:[133X
  
  [30X    [33X[0;6YIt first determines the color class for each point [10Xj[110X in [10X[1..[3Xn[103X[10X][110X.[133X
  
  [30X    [33X[0;6YIt   computes   the  inverse  of  [3Xp[103X,  let  this  be  [10Xp_inv[110X.  The  list
        [10XListPerm(p_inv,  n)[110X  gives  the order in which points [10Xval[110X appear if we
        iterate [10Xi[110X from [10X1[110X to [10Xn[110X and take [10Xval = i^(p_inv)[110X.[133X
  
  [30X    [33X[0;6YIt  then  constructs  a  new  permutation.  For each [10Xi[110X from [10X1[110X to [10Xn[110X, it
        considers  the  point  [10Xval = i^(p_inv)[110X. This point [10Xval[110X belongs to some
        color class, say [10Xcol_val[110X.[133X
  
  [30X    [33X[0;6YThe  point  [10Xval[110X is mapped by the new permutation to the next available
        (i.e.,   smallest   unassigned)  point  within  its  own  color  class
        [10X[3Xcolours[103X[10X[col_val][110X,  according  to  the  ordering  defined  by iterating
        through [10Xi[110X.[133X
  
  [33X[0;0YThe  effect  is  that  the  output permutation, when applied, will order the
  points  such  that  all  points of the first color class come first (ordered
  among themselves by their [10Xp_inv[110X values), then all points of the second color
  class (similarly ordered), and so on.[133X
  
