Lx      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw+Anders Claesson <anders.claesson@gmail.com>None5By 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 right-to-left minima. $The number of right-to-left 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 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 components. .Rank as defined by Elizalde & Pak. /%Dimension (largest non-fixed-point). 0One pass of stack-sort. 1One pass of bubble-sort. 2Lexicographically, the next x with the same Hamming weight. 3 onesCUInt k m gives the k( smallest indices whose bits are set in m. 4JLexicographically, the next integral number with the same Hamming weight. Pyz{|}~  !"#$%&'()*+,-./012345  !"#$%&'()*+,-./012345  +,!"#$%&'()*-./01324Pyz{|}~  !"#$%&'()*+,-./01234+Anders Claesson <anders.claesson@gmail.com>NoneBLexicographically, 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..] 5=A set is represented by an increasing vector of non-negative  integers. 68The class of permutations. Minimal complete definition: 7 and  8!. The default implementations of 9 and : can be ; somewhat slow, so you may want to implement them as well. 7: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 8 A (left)  group action of = on a. As for any group  action it should hold that I (u `act` v) `act` w == u `act` (v `act` w) && idperm u `act` v == v 9CThe size of a permutation. The default implementation derived from   size == size . st %This is not a circular definition as 9 on = is 5 implemented independently. If the implementation of 7 is ; slow, then it can be worth while to override the standard < definiton; any implementation should, however, satisfy the  identity above. :;The identity permutation on the same underlying set as the ( given permutation. It should hold that   st (idperm u) == idperm (st u) .Group theoretically, it should also hold that u . inverse u ==  idperm u*. In terms of the group action this means  $ idperm u == inverse (st u) `act` u (and this is the default implementation. ;3The group theoretical inverse. It should hold that  , inverse u == inverse (st u) `act` idperm u (and this is the default implementation. <.Predicate determining if two permutations are 3 order-isomorphic. The default implementation uses   u `ordiso` v == u == st v Equivalently, one could use 1 u `ordiso` v == inverse u `act` v == idperm v =By a standard permutation! we shall mean a permutations of  [0..k-1]. >,Convert a standard permutation to a vector. ?CConvert 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. @*Convert a standard permutation to a list. A<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. BThe skew sum+ of two permutations. (A definition of the   direct sum is provided by  of the  instance for =.) CunrankStPerm 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] DQThe list of standard permutations of the given size (the symmetric group). E.g., + sym 2 == [fromList [0,1], fromList [1,0]] EGeneralize a function on =$ to a function on any permutations:  * generalize f v = f (st v) `act` idperm v -Note that this will only work as intended if f is size preserving. FunrankPerm u rank is the rank -th (Myrvold & Ruskey)  permutation of u. E.g., , unrankPerm ['1'..'9'] 88888 == "561297843" G randomPerm u is a random permutation of u. H/All permutations of a given permutation. E.g., 6 perms "123" == ["123","213","321","132","231","312"] IOne pass of stack-sort. JOne pass of bubble-sort. K 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]] L avoids w ps is a predicate determining if w avoids the patterns ps. M avoiders ps v is the list of permutations of v avoiding the  patterns ps'. This is equivalent to the definition  $ avoiders ps = filter (`avoids` ps) but is usually much faster. Nav 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] O:A predicate determining if a given permutation is simple. P subsets n k is the list of subsets of [0..n-1] with k  elements. *56789:;<=>?@ABCDEFGHIJKLMNOP56789:;<=>?@ABCDEFGHIJKLMNOP=>?@ABCD6789:;<EFGHIJKLMNO5P 56789:;<=>?@ABCDEFGHIJKLMNOP+Anders Claesson <anders.claesson@gmail.com>NoneQ,Ration by 0 degrees, i.e. the identity map. R Ration by 90 degrees clockwise. S(Ration by 2*90 = 180 degrees clockwise. T(Ration by 3*90 = 270 degrees clockwise. U2Reflection through a horizontal axis (also called ^). V0Reflection through a vertical axis (also called _). W2Reflection through the main diagonal (also called `). X&Reflection through the anti-diagonal. YEThe dihedral group of order 8 (the symmetries of a square); that is, ' d8 = [r0, r1, r2, r3, s0, s1, s2, s3] Z: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 functions in fs. E.g., 6 orbit klein4 "2314" == ["1423","2314","3241","4132"] \ id = r0]  rotate = r1^ complement = s0_  reverse = s1`  inverse = s2QRSTUVWXYZ[\]^_`QRSTUVWXYZ[\]^_`QRSTUVWXYZ[\]^_`QRSTUVWXYZ[\]^_`+Anders Claesson <anders.claesson@gmail.com>NoneaThe number of ascents. An ascent in w is an index i such  that w[i] < w[i+1]. bThe number of descents. A descent in w is an index i such  that w[i] > w[i+1]. cThe number of  excedances : positions i such that w[i] > i; dThe number of  fixed points : positions i such that w[i] == i; eThe number of  inversions: pairs (i,j) such that i < j and w[i] > w[j] fThe major index is the sum of descents. gThe number of peaks : positions i such that w[i-1] < w[i] and w[i] > w[i+1]. hThe number of valleys : positions i such that w[i-1] > w[i] and w[i] < w[i+1]. iThe number of double ascents : positions i such that w[i-1] < w[i] < w[i+1]. jThe number of double descents : positions i such that w[i-1] > w[i] > w[i+1]. kThe number of left-to-right minima : positions i such that w[i] < w[j] for all j < i. lThe number of left-to-right maxima : positions i such that w[i] > w[j] for all j < i. mThe number of right-to-left minima : positions i such that w[i] < w[j] for all j > i. nThe number of right-to-left maxima : positions i such that w[i] > w[j] for all j > i. o<The first (left-most) element in the standardization. E.g., head "231" = head (fromList [1,2,0]) = 1. p<The last (right-most) element in the standardization. E.g., last "231" = last (fromList [1,2,0]) = 0. q0Length of the left-most increasing run: largest i such that  w[0] < w[1] < ... < w[i-1]. r0Length of the left-most decreasing run: largest i such that  w[0] > w[1] > ... > w[i-1]. s1Length of the right-most increasing run: largest i such that  w[n-i] < ... < w[n-2] < w[n-1]. t1Length of the right-most decreasing run: largest i such that  w[n-i] > ... > w[n-2] > w[n-1]. u 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]. v8The 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 ] w9The dimension of a permutation is defined as the largest 3 non-fixed-point, or zero if all points are fixed. abcdefghijklmnopqrstuvwabcdefghijklmnopqrstuvwabcdefghijklmnopqrstuvwabcdefghijklmnopqrstuvw      !"#$%&'()*+,-./0123456789:; <=>  ?@AB56CDEFGHIJKLMNOPQR$%01&'()*+,- !./"#234STUVWXYZ[\]^_`abcdefghijklmnopqrSstSsuv<wxyz{|}~Asym-0.2Math.Sym.InternalMath.Sym Math.Sym.D8 Math.Sym.StatPerm0 LehmercodeunrankLehmercodefromLehmercoderandomLehmercode lehmercodessizetoListfromListact unrankPerm randomPermsymidperm revIdpermstistordisosimplecopiesavoidersreverse complementinverserotateheadlastrminrmaxrirrdrascdesinvmajpeakvalldascddeslminlmaxlirldrexcfpcompepdim stackSort bubbleSort nextCUInt onesCUInt nextIntegralSetPermStPermtoVector fromVector/-/ unrankStPerm generalizepermscopiesOfavoidsavsubsetsr0r1r2r3s0s1s2s3d8klein4orbitidbaseForeign.C.TypesCUIntc_onesc_next c_bubblesort c_stacksortc_dimc_epc_compc_ldrc_lirc_lmaxc_lminc_ddesc_dascc_vallc_peakc_majc_invc_fpc_excc_desc_ascc_simplec_ordiso factorial avoiders1statsortopnextones Data.MonoidmappendMonoidBitmaskperm0act'bitmasks$fBitmaskInteger$fBitmaskCUInt$fPerm[] $fPermStPerm$fMonoidStPerm $fShowStPerm $fOrdStPerm