“      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~+Anders Claesson <anders.claesson@gmail.com>None>By 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. act u v is the permutation w defined by w(u(i)) = v(i). 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. /The number of components. 0 The number of skew components. 1Rank as defined by Elizalde & Pak. 2%Dimension (largest non-fixed-point). 3The number of small ascents. 4The number of small descents. 5,The set of indices of left-to-right maxima. 6,The set of indices of right-to-left maxima. 7"The set of indices of components. 8One pass of stack-sort. 9One pass of bubble-sort. :'Delete the element at a given position ;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:;<=>  !"#$%&'()*+,-./0123456789:;<=>  ,-.!"#$%&'()*+/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 set is represented by an increasing vector of non-negative  integers. ?8The class of permutations. Minimal complete definition: @  A and C!. The default implementations of B and  D4 can be somewhat slow, so you may want to implement  them as well. @: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 A A (left)  group action of G on a. As for any group  action it should hold that M (u `act` v) `act` w == u `act` (v `act` w) && neutralize u `act` v == v BCThe size of a permutation. The default implementation derived from   size == size . st %This is not a circular definition as B on G is 5 implemented independently. If the implementation of @ is ; slow, then it can be worth while to override the standard < definiton; any implementation should, however, satisfy the  identity above. C,The identity permutation of the given size. D<The permutation obtained by acting on the given permutation @ with its own inverse; that is, the identity permutation on the > same underlying set as the given permutation. It should hold  that  ( st (neutralize u) == neutralize (st u) ( neutralize u == inverse (st u) `act` u ! neutralize u == idperm (size u) CThe default implementation uses the last of these three equations. E3The group theoretical inverse. It should hold that  0 inverse u == inverse (st u) `act` neutralize u (and this is the default implementation. F.Predicate determining if two permutations are 3 order-isomorphic. The default implementation uses   u `ordiso` v == u == st v Equivalently, one could use 5 u `ordiso` v == inverse u `act` v == neutralize v GBy a standard permutation! we shall mean a permutations of  [0..k-1]. H,Convert a standard permutation to a vector. ICConvert a vector to a standard permutation. The vector should be a  permutation of the elements [0..k-1] for some positive k. No  checks for this are done. J*Convert a standard permutation to a list. K<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. LThe skew sum+ of two permutations. (A definition of the   direct sum is provided by  of the  instance for G.) M:The bijective function defined by a standard permutation. NunrankStPerm n rank is the rank -th (Myrvold & Ruskey)  permutation of [0..n-1]. E.g., N unrankStPerm 16 19028390 == fromList [6,15,4,11,7,8,9,2,5,0,10,3,12,13,14,1] OQThe list of standard permutations of the given size (the symmetric group). E.g., + sym 2 == [fromList [0,1], fromList [1,0]] PGeneralize a function on G$ to a function on any permutations:  . generalize f v = f (st v) `act` neutralize v -Note that this will only work as intended if f is size preserving. QunrankPerm u rank is the rank -th (Myrvold & Ruskey)  permutation of size n. E.g., # unrankPerm 9 88888 == "561297843" R randomPerm n! is a random permutation of size n. S(All permutations of a given size. E.g., 2 perms 3 == ["123","213","321","132","231","312"] TOne pass of stack-sort. UOne pass of bubble-sort. V copiesOf p w3 is the list of (indices of) copies of the pattern  p in the permutation w. E.g., \ copiesOf (st "21") "2431" == [fromList [1,2],fromList [0,3],fromList [1,3],fromList [2,3]] W avoids w ps is a predicate determining if w avoids the patterns ps. Xavoiders ps vs is the list of permutations in vs avoiding the  patterns ps'. This is equivalent to the definition  $ avoiders ps = filter (`avoids` ps) but is usually much faster. Yav ps n is the list of permutations of [0..n-1] avoiding the  patterns ps. E.g., H map (length . av [st "132", st "321"]) [1..8] == [1,2,4,7,11,16,22,29] Z'Delete the element at a given position ['The list of all single point deletions \?Extend a permutation by inserting a new largest element at the  given position ](The list of all single point extensions ^,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. a,The set of indices of right-to-left minima. b"The set of indices of components. c'The set of indices of skew components. d:A predicate determining if a given permutation is simple. e subsets n k is the list of subsets of [0..n-1] with k  elements. 9>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde(>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde(GHIJKLMNO?@ABCDEFPQRSTUVWXYZ[\]^_`abcd>e.>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde+Anders Claesson <anders.claesson@gmail.com>Nonef,Ration by 0 degrees, i.e. the identity map. g Ration by 90 degrees clockwise. h(Ration by 2*90 = 180 degrees clockwise. i(Ration by 3*90 = 270 degrees clockwise. j2Reflection through a horizontal axis (also called s). k0Reflection through a vertical axis (also called t). l2Reflection through the main diagonal (also called u). m&Reflection through the anti-diagonal. nEThe dihedral group of order 8 (the symmetries of a square); that is, ' d8 = [r0, r1, r2, r3, s0, s1, s2, s3] o:The Klein four-group (the symmetries of a non-equilateral  rectangle); that is,  klein4 = [r0, r2, s0, s1] p orbit fs x is the orbit of x under the functions in fs. E.g., 6 orbit klein4 "2314" == ["1423","2314","3241","4132"] q id = r0r  rotate = r1s complement = s0t  reverse = s1u  inverse = s2fghijklmnopqrstufghijklmnopqrstufghijklmnopqrstufghijklmnopqrstu+Anders Claesson <anders.claesson@gmail.com>NonevThe number of ascents. An ascent in w is an index i such  that w[i] < w[i+1]. wThe number of descents. A descent in w is an index i such  that w[i] > w[i+1]. xThe number of  excedances : positions i such that w[i] > i. yThe number of  fixed points : positions i such that w[i] == i. zThe 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. vwxyz{|}~vwxyz{|}~vwxyz{|}~vwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCD EFGH  IJKLM=>NOP?QRS:T;U<VWXYZ[\]^_`abc$%123&'()*+,-. !/0"#456789defghijklmnopqrstuvwxyz{|}~eeFL sym-0.4.1Math.Sym.InternalMath.Sym Math.Sym.D8 Math.Sym.StatPerm0 LehmercodeunrankLehmercodefromLehmercoderandomLehmercode lehmercodessizetoListfromListact unrankPerm randomPermsymidperm revIdpermstistordisosimplecopiesavoidersreverse complementinverserotateheadlastrminrmaxrirrdrascdesinvmajcomajpeakvalldascddeslminlmaxlirldrexcfpcyccompscompepdimasc0des0lMaximarMaxima components stackSort bubbleSortdel nextCUInt onesCUInt nextIntegralSetPerm neutralizeStPermtoVector fromVector/-/ bijection unrankStPerm generalizepermscopiesOfavoidsavshadowextcoshadowlMinimarMinimaskewComponentssubsetsr0r1r2r3s0s1s2s3d8klein4orbitidshadbaseForeign.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 avoiders1statsortopnextones Data.MonoidmappendMonoidBitmaskperm0act'stLactLbitmasks$fBitmaskInteger$fBitmaskCUInt$fPerm[] $fPerm[]0 $fPermStPerm$fMonoidStPerm $fShowStPerm $fOrdStPerm