OKlibrary  0.2.1.6
SymmetricGroups.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 6.7.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2011, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Semigroups/TransformationMonoids.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00026 
00027 
00028 /* **************************
00029    * Permutations as lists *
00030    **************************
00031 */
00032 
00033 permutation_l_inv(n) := buildq([n],
00034  lambda([p], ary2l(osm2ary_lt(l2osm_inv(p), n, fixnum))))$
00035 
00036 /* The symmetric group with n (>= 0) elements, as submonoid of the full
00037    transformation monoid trf_l_mon(n):
00038 */
00039 sym_l_ugrp(n) :=
00040  [permutations(setn(n)),
00041   transformation_l_compo,
00042   create_list(i,i,1,n)]$
00043 sym_l_ugrpi(n) := endcons(permutation_l_inv(n), sym_l_ugrp(n))$
00044 /* Lexicographical order: */
00045 sym_l_ougrp(n) :=
00046  [listify(permutations(setn(n))),
00047   transformation_l_compo,
00048   create_list(i,i,1,n)]$
00049 
00050 
00051 /* **********************
00052    * Cycle presentation *
00053    **********************
00054 */
00055 
00056 /* A "cycle presentation" of some permutation over {1,...,n} is a
00057    set of repetition-free lists, each list starting with its smallest
00058    element, so that these lists as sets are a partitioning of {1,...,n}.
00059 */
00060 
00061 /* For a permutation over {1,...,n} as function/list compute the
00062    cycle presentation (a set of lists, each list representing a
00063    cyle, standardised to start with the smallest element):
00064 */
00065 cyclepres_pmtf(p,n) := block([res:{}, rem:setn(n)],
00066  while not emptyp(rem) do block([x : lmin(rem), C, y],
00067    C : [x],
00068    y : p(x),
00069    while y#x do (
00070      C : cons(y, C),
00071      y : p(y)
00072    ),
00073    res : adjoin(reverse(C),res),
00074    rem : setdifference(rem,setify(C))
00075  ),
00076  res)$
00077 cyclepres_perl(p) := cyclepres_pmtf(trfl2trff(p), length(p))$
00078 
00079 /* Inversely, for a cycle presentation c over {1,...,n} compute the
00080    corresponding permutation as a hash-map resp. as a list:
00081 */
00082 cyclepres2hm(c) := block([h : sm2hm({})],
00083   for C in c do h : compose_hm_sm(h, map("[",C,rotate(C,-1))), h)$
00084 cyclepres2perl(c) := block([h : cyclepres2hm(c)],
00085   create_list(ev_hm(h,i),i,1,sum_l(map(length,listify(c)))))$
00086 
00087 /* Remark: cyclepres_perl(cyclepres2perl(c)) = c and
00088            cyclepres2perl(cyclepres_perl(p)) = p.
00089 */
00090 
00091 /* The cycle-type of a permutation as function/list: */
00092 cycletype_pmtf(p,n) :=
00093   list_distribution(map(length,listify(cyclepres_pmtf(p,n))))$
00094 cycletype_perl(p) := cycletype_pmtf(trfl2trff(p), length(p))$
00095 
00096 /* Note that two permutations over {1,...,n} are conjugated iff their
00097    cycle-types are equal.
00098 */
00099 
00100 /* For conversions between transformations as lists and as functions see
00101    Algebra/Lisp/Groupoids/Semigroups/TransformationMonoids.mac.
00102 */
00103 
00104 
00105 /* ********************
00106    * Basic operations *
00107    ********************
00108 */
00109 
00110 oklib_plain_include(functs)$ /* for lcm */
00111 
00112 /* Computing the order of a permutation as function/list: */
00113 order_element_pmtf(p,n) :=
00114   apply(lcm, map(length,listify(cyclepres_pmtf(p,n))))$
00115 order_element_perl(p) := order_element_pmtf(trfl2trff(p), length(p))$
00116 
00117 /* The inversion-vector of permutation p as list (of the same length, with
00118    trailing zero, counting for each position the number of smaller elements
00119    to the right):
00120 */
00121 inversion_vector_perl(p) := if emptyp(p) then [] else
00122  cons(countlt_l(first(p),rest(p)), inversion_vector_perl(rest(p)))$
00123 /* The inverse operation, computing the permutation as list of an
00124    inversion-vector: */
00125 perl_inversion_vector(v) := if emptyp(v) then [] else
00126  block([x : first(v)+1],
00127   cons(x,
00128     map(lambda([y], if y >= x then y+1 else y),
00129         perl_inversion_vector(rest(v)))))$
00130 
00131 
00132 /* The number of involutions (self-inverse permutations) of the
00133    symmetric group:
00134 */
00135 numinvolutions_symgrp(n) := if n<=1 then 1 else
00136  numinvolutions_symgrp(n-1) + (n-1) * numinvolutions_symgrp(n-2)$
00137 /* This is http://oeis.org/A000085 . */
00138