๚ฮยจนoƒ      !"#$%&'()*+,-./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 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). 0The number of small ascents. 1The number of small descents. 2+The list of values of left-to-right minima 3,The list of indices of left-to-right minima 4One pass of stack-sort. 5One pass of bubble-sort. 6'Delete the element at a given position 7Lexicographically, the next ƒ with the same Hamming weight. 8 onesCUInt k m gives the k( smallest indices whose bits are set in m. 9JLexicographically, the next integral number with the same Hamming weight. Z„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œž Ÿ  ก !"#$%&'()*+,-./01ข23ฃ456789:  !"#$%&'()*+,-./0123456789:  +,!"#$%&'()*-./0123456879Z„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œž Ÿ  ก !"#$%&'()*+,-./01ข23ฃ456789+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: < and  =!. The default implementations of > and ? 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 (left)  group action of B 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 >CThe size of a permutation. The default implementation derived from   size == size . st %This is not a circular definition as > on B 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. ?;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. A.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 BBy a standard permutation! we shall mean a permutations of  [0..k-1]. C,Convert a standard permutation to a vector. DCConvert 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. E*Convert a standard permutation to a list. F<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. GThe skew sum+ of two permutations. (A definition of the   direct sum is provided by ฆ of the ง instance for B.) HunrankStPerm 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] IQThe list of standard permutations of the given size (the symmetric group). E.g., + sym 2 == [fromList [0,1], fromList [1,0]] JGeneralize a function on B$ 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. KunrankPerm u rank is the rank -th (Myrvold & Ruskey)  permutation of u. E.g., , unrankPerm ['1'..'9'] 88888 == "561297843" L randomPerm u is a random permutation of u. M/All permutations of a given permutation. E.g., 6 perms "123" == ["123","213","321","132","231","312"] NOne pass of stack-sort. OOne pass of bubble-sort. P 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]] Q avoids w ps is a predicate determining if w avoids the patterns ps. R 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. Sav 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] T'Delete the element at a given position U'The list of all single point deletions V:A predicate determining if a given permutation is simple. W subsets n k is the list of subsets of [0..n-1] with k  elements. ,จคฅ:;<=>?@ABฉชCDEFGHIซJKLMNOPQRSTUVฌWญฎฏฐฑฒณ:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWBCDEFGHI;<=>?@AJKLMNOPQRSTUV:W"จคฅ:;<=>?@ABฉชCDEFGHIซJKLMNOPQRSTUVฌWญฎฏฐฑฒณ+Anders Claesson <anders.claesson@gmail.com>NoneX,Ration by 0 degrees, i.e. the identity map. Y Ration by 90 degrees clockwise. Z(Ration by 2*90 = 180 degrees clockwise. [(Ration by 3*90 = 270 degrees clockwise. \2Reflection through a horizontal axis (also called e). ]0Reflection through a vertical axis (also called f). ^2Reflection through the main diagonal (also called g). _&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] a:The Klein four-group (the symmetries of a non-equilateral  rectangle); that is,  klein4 = [r0, r2, s0, s1] b orbit fs x is the orbit of x under the functions in fs. E.g., 6 orbit klein4 "2314" == ["1423","2314","3241","4132"] c id = r0d  rotate = r1e complement = s0f  reverse = s1g  inverse = s2XYZ[\]^_`abcdefgXYZ[\]^_`abcdefgXYZ[\]^_`abcdefgXYZ[\]^_`abcdefg+Anders Claesson <anders.claesson@gmail.com>NonehThe number of ascents. An ascent in w is an index i such  that w[i] < w[i+1]. iThe number of descents. A descent in w is an index i such  that w[i] > w[i+1]. jThe number of  excedances : positions i such that w[i] > i; kThe number of  fixed points : positions i such that w[i] == i; lThe number of  inversions: pairs (i,j) such that i < j and w[i] > w[j] mThe major index is the sum of descents. nThe number of peaks : positions i such that w[i-1] < w[i] and w[i] > w[i+1]. oThe number of valleys : positions i such that w[i-1] > w[i] and w[i] < w[i+1]. pThe number of double ascents : positions i such that w[i-1] < w[i] < w[i+1]. qThe number of double descents : positions i such that w[i-1] > w[i] > w[i+1]. rThe number of left-to-right minima : positions i such that w[i] < w[j] for all j < i. sThe number of left-to-right maxima : positions i such that w[i] > w[j] for all j < i. tThe number of right-to-left minima : positions i such that w[i] < w[j] for all j > i. uThe number of right-to-left maxima : positions i such that w[i] > w[j] for all j > i. v<The first (left-most) element in the standardization. E.g., head "231" = head (fromList [1,2,0]) = 1. w<The last (right-most) element in the standardization. E.g., last "231" = last (fromList [1,2,0]) = 0. x0Length of the left-most increasing run: largest i such that  w[0] < w[1] < ... < w[i-1]. y0Length of the left-most decreasing run: largest i such that  w[0] > w[1] > ... > w[i-1]. z1Length 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]. }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 list of values of left-to-right minima ‚,The list of indices of left-to-right minima ดhijklmnopqrstuvwxyz{|}~€‚hijklmnopqrstuvwxyz{|}~€‚hijklmnopqrstuvwxyz{|}~€‚ดhijklmnopqrstuvwxyz{|}~€‚ต      !"#$%&'()*+,-./0123456789:;<=>?@ ABC  DEFG9:HIJ;KLMNOPQRSTUVWX$%01&'()*+,- !./"#2345678YZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}Y~Y~€A‚ƒ„…†‡ˆ‰Š‹FŒ sym-0.2.2Math.Sym.InternalMath.Sym Math.Sym.D8 Math.Sym.StatPerm0 LehmercodeunrankLehmercodefromLehmercoderandomLehmercode lehmercodessizetoListfromListact unrankPerm randomPermsymidperm revIdpermstistordisosimplecopiesavoidersreverse complementinverserotateheadlastrminrmaxrirrdrascdesinvmajpeakvalldascddeslminlmaxlirldrexcfpcompepdimasc0des0 lminValues lminIndices stackSort bubbleSortdel nextCUInt onesCUInt nextIntegralSetPermStPermtoVector fromVector/-/ unrankStPerm generalizepermscopiesOfavoidsavshadowsubsetsr0r1r2r3s0s1s2s3d8klein4orbitidbaseForeign.C.TypesCUIntc_onesc_next c_bubblesort c_stacksortc_lmin_indices c_lmin_valuesc_des0c_asc0c_dimc_epc_compc_ldrc_lirc_lmaxc_lminc_ddesc_dascc_vallc_peakc_majc_invc_fpc_excc_desc_ascc_simplec_ordiso factorial avoiders1statrecordsortopnextones Data.MonoidmappendMonoidBitmaskperm0act'bitmasks$fBitmaskInteger$fBitmaskCUInt$fPerm[] $fPermStPerm$fMonoidStPerm $fShowStPerm $fOrdStPerm