5      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~+Anders Claesson <anders.claesson@gmail.com>NoneABy convention, a member of Perm0 is a permutation of some  finite subset of [0..]. %A Lehmercode is a vector of integers w such w!i <= length w - 1 - i  for each i in [0..length w - 1]. unrankLehmercode n rank is the rank-th Lehmercode of length n. )Build a permutation from its Lehmercode. )A random Lehmercode of the given length. +The list of Lehmercodes of a given length. 3The size of a permutation; the number of elements. %The list of images of a permutation. *Make a permutation from a list of images. u   v is the permutation w defined by w(u(i)) = v(i).  inflate w vs is the  inflation of w by vs. unrankPerm n rank is the rank -th (Myrvold & Ruskey) permutation of length n. *A random permutation of the given length. sym n is the list of permutations of [0..n-1] (the symmetric group). .The identity permutation of the given length. )The reverse of the identity permutation. sti w* is the inverse of the standardization of w (a  permutation on [0..length w-1] ). E.g., sti <4,9,2> ==  <2,0,1>. The standardization map.  ordiso u v m# determines whether the subword in v specified by  m is order isomorphic to u. simple w determines whether w is simple copies subsets p w2 is the list of bitmasks that represent copies of p in w. avoiders subsets st ps ws is the list of permutations in ws  avoiding the patterns in ps. reverse < a_1,...,a_n> == < a_n,,...,a_1>. E.g., reverse  <9,3,7,2> == <2,7,3,9>.  complement < a_1,...,a_n> == < b_1,,...,b_n>, where b_i = n - a_i - 1.  E.g.,  complement < 3,4,0,1,2> == < 1,0,4,3,2>.  inverse w% is the group theoretical inverse of w. E.g.,  inverse <1,2,0> == <2,0,1>. 3The clockwise rotatation through 90 degrees. E.g.,  rotate <1,0,2> == <1,2,0>. *First (left-most) value of a permutation. *Last (right-most) value of a permutation. $The number of left-to-right minima. $The number of left-to-right maxima. The right-most increasing run. The right-most decreasing run. The number of ascents. !The number of descents. "The number of inversions. #The major index. $The co-major index. %The number of peaks. &The number of valleys. 'The number of double ascents. (The number of double descents. )$The number of left-to-right minima. *$The number of left-to-right maxima. +The left-most increasing run. ,The left-most decreasing run. -The number of excedances. .The number of fixed points. /The number of cycles. 0The number of components. 1 The number of skew components. 2Rank as defined by Elizalde & Pak. 3%Dimension (largest non-fixed-point). 4The number of small ascents. 5The number of small descents. 6,The set of indices of left-to-right maxima. 7,The set of indices of right-to-left maxima. 8"The set of indices of components. 9One pass of stack-sort. :One pass of bubble-sort. ;'Delete the element at a given position <8The Simion-Schmidt bijection from Av(123) onto Av(132). =>The inverse of the Simion-Schmidt bijection. It is a function  from Av(132) to Av(123). >Lexicographically, the next  with the same Hamming weight. ? onesCUInt k m gives the k( smallest indices whose bits are set in m. @JLexicographically, the next integral number with the same Hamming weight. `  !"#$%&'()*+,-./0123456789:;<=>?@A  !"#$%&'()*+,-./0123456789:;<=>?@A  !-./"#$%&'()*+,0123456789:;<=?>@`  !"#$%&'()*+,-./0123456789:;<=>?@+Anders Claesson <anders.claesson@gmail.com>None?BLexicographically, the next bitmask with the same Hamming weight. ones k m- is the set of indices whose bits are set in  m. Default implementation: < ones m = fromListN (popCount m) $ filter (testBit m) [0..] A=A set is represented by an increasing vector of non-negative  integers. B2All methods of the Pattern typeclass have default C implementations. This is because any permutation can also be seen B as a pattern. If you want to override the default implementation  you should at least define C. C copiesOf p w1 is the list of indices of copies of the pattern  p in the permutation w. E.g., W copiesOf "21" "2431" == [fromList [1,2],fromList [0,3],fromList [1,3],fromList [2,3]] Dw D p is a predicate determining if w contains the pattern p. Ew E p is a predicate determining if w avoids the pattern p. Fw F ps is a predicate determining if w avoids the patterns ps. Gavoiders ps vs is the list of permutations in vs avoiding the  patterns ps. The default definition is ' avoiders ps = filter (`avoidsAll` ps) HType alias for  IntMap Int. This can be thought of as a $ permutations in two line notation. K,A list of integers viewed as a permutation. NAA String viewed as a permutation of its characters. The alphabet  is ordered as % ['1'..'9'] ++ ['A'..'Z'] ++ ['a'..] Q8The class of permutations. Minimal complete definition: R,  S and U . The default implementation of T can be 9 somewhat slow, so you may want to implement it as well. R:The standardization map. If there is an underlying linear  order on a then st# is determined by the unique order  preserving map from [0..]! to that order. In any case, the ? standardization map should be equivariant with respect to the 7 group action defined below; i.e., it should hold that  st (u `act` v) == u `act` st v S A (left)  group action of Z on a. As for any group  action it should hold that  I (u `act` v) `act` w == u `act` (v `act` w) && idperm n `act` v == v where v,w::a and  u::StPerm are of size n. TCThe size of a permutation. The default implementation derived from   size == size . st %This is not a circular definition as T on Z is 5 implemented independently. If the implementation of R is ; slow, then it can be worth while to override the standard < definiton; any implementation should, however, satisfy the  identity above. U,The identity permutation of the given size. V3The group theoretical inverse. It should hold that   inverse == unst . inverse . st (and this is the default implementation. W.Predicate determining if two permutations are 3 order-isomorphic. The default implementation uses   u `ordiso` v == u == st v Equivalently, one could use 8 u `ordiso` v == inverse u `act` v == idperm (size u) X<The inverse of the standardization function. For efficiency A reasons we make the size of the permutation an argument to this  function. It should hold that   unst n w == w `act` idperm n >and this is the default implementation. An un-standardization 0 function without the size argument is given by Y below. YThe inverse of R. It should hold that   unst w == unstn (size w) w (and this is the default implementation. ZBy a standard permutation! we shall mean a permutations of  [0..k-1]. [*Convert a standard permutation to a list. \<Convert a list to a standard permutation. The list should a  permutation of the elements [0..k-1] for some positive k. No  checks for this are done. ]QThe list of standard permutations of the given size (the symmetric group). E.g., + sym 2 == [fromList [0,1], fromList [1,0]] ^The empty permutation. _The one letter permutation. `#Convert a permutation to a vector. a:Convert a vector to a permutation. The vector should be a  permutation of the elements [0..k-1] for some positive k. No  checks for this are done. b1The bijective function defined by a permutation. cLift a function on ' Vector Int'$ to a function on any permutations: $ lift f = fromVector . f . toVector dLike c$ but for functions of two variables e@Sort a list of permutations with respect to the standardization  and remove duplicates f*Cast a permutation of one type to another gThe  direct sum of two permutations. h*The direct sum of a list of permutations. iThe skew sum of two permutations. j(The skew sum of a list of permutations. k inflate w vs is the  inflation of w by vs . It is the  permutation of length sum (map size vs) obtained by replacing  each entry w!i, by an interval that is order isomorphic to vs!i : in such a way that the intervals are order isomorphic to w. In  particular,  u /+/ v == inflate "12" [u,v]  u \-\ v == inflate "21" [u,v] lunrankPerm u rank is the rank -th (Myrvold & Ruskey)  permutation of size n. E.g., # unrankPerm 9 88888 == "561297843" m randomPerm n! is a random permutation of size n. n(All permutations of a given size. E.g., 2 perms 3 == ["123","213","321","132","231","312"] oOne pass of stack-sort. pOne pass of bubble-sort. qstat p is the pattern p when regarded as a statistic/ function  counting copies of itself:  stat p = length . copiesOf p rav ps n is the list of permutations of [0..n-1] avoiding the  patterns ps. E.g., A map (length . av ["132","321"]) [1..8] == [1,2,4,7,11,16,22,29] sLike r1 but the return type is any set of permutations. t'Delete the element at a given position u'The list of all single point deletions v?The list of permutations that are contained in at least one of  the given permutaions w ext i j w extends w by inserting a new element of  (relative) size j at position i. It should hold that  0 <= i,j <= size w. x(The list of all single point extensions y9The set of minimal elements with respect to containment. z9The set of maximal elements with respect to containment. { coeff f v is the coefficient of v when expanding the  permutation statistic f as a sum of permutations/patterns. See E Petter Brndn and Anders Claesson: Mesh patterns and the expansion @ of permutation statistics as sums of permutation patterns, The 3 Electronic Journal of Combinatorics 18(2) (2011),   Dhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p5. |,The set of indices of left-to-right maxima. },The set of indices of left-to-right minima. ~,The set of indices of right-to-left maxima. ,The set of indices of right-to-left minima. "The set of indices of components. 'The set of indices of skew components. :A predicate determining if a given permutation is simple.  subsets n k is the list of subsets of [0..n-1] with k  elements. eABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~CABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~CZ[\]QRSTUVWXYNOPKLMHIJ^_`abcdefghijklmnopBCDEFGqrstuvwxyz{|}~ANABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~+Anders Claesson <anders.claesson@gmail.com>None,Ration by 0 degrees, i.e. the identity map.  Ration by 90 degrees clockwise. (Ration by 2*90 = 180 degrees clockwise. (Ration by 3*90 = 270 degrees clockwise. 2Reflection through a horizontal axis (also called ). 0Reflection through a vertical axis (also called ). 2Reflection through the main diagonal (also called ). &Reflection through the anti-diagonal. EThe dihedral group of order 8 (the symmetries of a square); that is, ' d8 = [r0, r1, r2, r3, s0, s1, s2, s3] :The Klein four-group (the symmetries of a non-equilateral  rectangle); that is,  klein4 = [r0, r2, s0, s1]  orbit fs x is the orbit of x under the group of function fs. E.g., 6 orbit klein4 "2314" == ["1423","2314","3241","4132"] symmetryClasses fs xs* is the list of equivalence classes under  the action of the group of functions fs. %Symmetry classes with respect to D8. (Symmetry classes with respect to Klein4 id = r0  rotate = r1 complement = s0  reverse = s1  inverse = s2+Anders Claesson <anders.claesson@gmail.com>NoneThe number of ascents. An ascent in w is an index i such  that w[i] < w[i+1]. The number of descents. A descent in w is an index i such  that w[i] > w[i+1]. The number of  excedances : positions i such that w[i] > i. The number of  fixed points : positions i such that w[i] == i. The number of cycles7: orbits of the permutation when viewed as a function. The number of  inversions: pairs (i,j) such that i < j and w[i] > w[j]. The major index is the sum of descents. The co-major index is the sum of descents. The number of peaks : positions i such that w[i-1] < w[i] and w[i] > w[i+1]. The number of valleys : positions i such that w[i-1] > w[i] and w[i] < w[i+1]. The number of double ascents : positions i such that w[i-1] < w[i] < w[i+1]. The number of double descents : positions i such that w[i-1] > w[i] > w[i+1]. The number of left-to-right minima : positions i such that w[i] < w[j] for all j < i. The number of left-to-right maxima : positions i such that w[i] > w[j] for all j < i. The number of right-to-left minima : positions i such that w[i] < w[j] for all j > i. The number of right-to-left maxima : positions i such that w[i] > w[j] for all j > i. <The first (left-most) element in the standardization. E.g., head "231" = head (fromList [1,2,0]) = 1. <The last (right-most) element in the standardization. E.g., last "231" = last (fromList [1,2,0]) = 0. 0Length of the left-most increasing run: largest i such that  w[0] < w[1] < ... < w[i-1]. 0Length of the left-most decreasing run: largest i such that  w[0] > w[1] > ... > w[i-1]. 1Length of the right-most increasing run: largest i such that  w[n-i] < ... < w[n-2] < w[n-1]. 1Length of the right-most decreasing run: largest i such that  w[n-i] > ... > w[n-2] > w[n-1].  The number of components. E.g., [2,0,3,1,4,6,7,5] has three  components: [2,0,3,1], [4] and [6,7,5]. %The number of skew components. E.g., [5,7,4,6,3,1,0,2] has three  skew components: [5,7,4,6], [3] and [1,0,2]. 8The rank as defined by Elizalde and Pak [Bijections for " refined restricted permutations, J. Comb. Theory, Ser. A, 2004]: 8 maximum [ k | k <- [0..n-1], w[i] >= k for all i < k ] 9The dimension of a permutation is defined as the largest 3 non-fixed-point, or zero if all points are fixed. The number of small ascents. A  small ascent in w is an index  i such that w[i] + 1 == w[i+1].  The number of small descents. A  small descent in w is an  index i such that w[i] == w[i+1] + 1. The size of the shadow of w#. That is, the number of different  one point deletions of w. +Anders Claesson <anders.claesson@gmail.com>None8The Simion-Schmidt bijection from Av(123) onto Av(132). >The inverse of the Simion-Schmidt bijection. It is a function  from Av(132) to Av(123). +Anders Claesson <anders.claesson@gmail.com>None&The class of increasing permutations. &The class of decreasing permutations.  Av(123).  Av(132).  Av(213). 7Av(231); also know as the stack sortable permutations.  Av(312).  Av(321). @The V-class is Av(132, 231). It is so named because the diagram < of a typical permutation in this class is shaped like a V. The "';-class is Av(213, 312). It is so named because the diagram 9 of a typical permutation in this class is shaped like a "'. @The >-class is Av(132, 312). It is so named because the diagram < of a typical permutation in this class is shaped like a >. The <;-class is Av(213, 231). It is so named because the diagram 9 of a typical permutation in this class is shaped like a <.  The union of , ,  and . GThe class of separable permutations; it is identical to Av(2413,3142).            !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNNOPPQRRST UVWXYZ[\]^_`abcde@AfghBijklmno=p>q?rstuvwxyz{|}~ '(456)*+,-./01#$!"23%&789:;<CDfWsym-0.8Math.Sym.InternalMath.Sym Math.Sym.D8 Math.Sym.StatMath.Sym.BijectionMath.Sym.ClassPerm0 LehmercodeunrankLehmercodefromLehmercoderandomLehmercode lehmercodessizetoListfromListactinflate unrankPerm randomPermsymidperm revIdpermstistordisosimplecopiesavoidersreverse complementinverserotateheadlastrminrmaxrirrdrascdesinvmajcomajpeakvalldascddeslminlmaxlirldrexcfpcyccompscompepdimasc0des0lMaximarMaxima components stackSort bubbleSortdel simionSchmidtsimionSchmidt' nextCUInt onesCUInt nextIntegralSetPatterncopiesOfcontainsavoids avoidsAllPerm2intmapIntPermintsCharPermcharsPermunstnunstStPermemptyonetoVector fromVector bijectionliftlift2 normalizecast/+/dsum\-\ssumpermsstatav permClassshadowdownsetextcoshadowminimamaximacoefflMinimarMinimaskewComponentssubsetsr0r1r2r3s0s1s2s3d8klein4orbitsymmetryClasses d8Classes klein4Classesidshadincdecav123av132av213av231av312av321veecaretgtltwedges separablesbaseForeign.C.TypesCUIntc_onesc_next c_bubblesort c_stacksortc_des0c_asc0c_dimc_epc_compc_ldrc_lirc_lmaxc_lminc_ddesc_dascc_vallc_peakc_comajc_majc_invc_cycc_fpc_excc_desc_ascc_simplec_ordiso factorial avoiders1sortopnextonesBitmaskperm0act'actLstString idpermString generalize generalize2bitmasks$fBitmaskInteger$fBitmaskCUInt$fPatternPerm2$fPatternIntPerm$fPatternCharPerm $fPattern[]$fPatternStPerm $fPermPerm2 $fOrdPerm2 $fShowPerm2 $fPermIntPerm $fOrdIntPerm $fShowIntPerm$fPerm[]$fPermCharPerm$fIsStringCharPerm $fOrdCharPerm$fShowCharPerm $fPermStPerm$fMonoidStPerm $fShowStPerm $fOrdStPermliftStat streamAv231 streamVeeunion compositions