úÎēMŠ?t      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs+Anders Claesson <anders.claesson@gmail.com>None3By 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. 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. .One pass of stack-sort. /One pass of bubble-sort. 0Lexicographically, the next t with the same Hamming weight. 1 onesCUInt k m gives the k( smallest indices whose bits are set in m. 2JLexicographically, the next integral number with the same Hamming weight. Luvwxyz{|}~€‚ƒ„…†‡ˆ‰ Š ‹Œ !"#$%&'()*+,-./0123  !"#$%&'()*+,-./0123 *+ !"#$%&'(),-./102Luvwxyz{|}~€‚ƒ„…†‡ˆ‰ Š ‹Œ !"#$%&'()*+,-./012+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..] 3=A set is represented by an increasing vector of non-negative  integers. 48The class of permutations. Minimal complete definition: 5 and  6!. The default implementations of 7 and 8 can be ; somewhat slow, so you may want to implement them as well. 5: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 6 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 7CThe size of a permutation. The default implementation derived from   size == size . st %This is not a circular definition as 7 on ; is 5 implemented independently. If the implementation of 5 is ; slow, then it can be worth while to override the standard < definiton; any implementation should, however, satisfy the  identity above. 8;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. 93The 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. ?<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. @The skew sum+ of two permutations. (A definition of the   direct sum is provided by  of the ‘ instance for ;.) AunrankStPerm 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] BQThe list of standard permutations of the given size (the symmetric group). E.g., + sym 2 == [fromList [0,1], fromList [1,0]] CGeneralize 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. DunrankPerm u rank is the rank -th (Myrvold & Ruskey)  permutation of u. E.g., , unrankPerm ['1'..'9'] 88888 == "561297843" E randomPerm u is a random permutation of u. F/All permutations of a given permutation. E.g., 6 perms "123" == ["123","213","321","132","231","312"] GOne pass of stack-sort. HOne pass of bubble-sort. I copies p w3 is the list of (indices of) copies of the pattern  p in the permutation w. E.g., Z copies (st "21") "2431" == [fromList [1,2],fromList [0,3],fromList [1,3],fromList [2,3]] J avoids ps w is a predicate determining if w avoids the patterns ps. K 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. Lav 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] M subsets n k is the list of subsets of [0..n-1] with k  elements. (’Ž3456789:;“”<=>?@AB•CDEFGHIJKL–M—˜™š›œ3456789:;<=>?@ABCDEFGHIJKLM;<=>?@AB456789:CDEFGHIJKL3M’Ž3456789:;“”<=>?@AB•CDEFGHIJKL–M—˜™š›œ+Anders Claesson <anders.claesson@gmail.com>NoneN,Ration by 0 degrees, i.e. the identity map. O Ration by 90 degrees clockwise. P(Ration by 2*90 = 180 degrees clockwise. Q(Ration by 3*90 = 270 degrees clockwise. R2Reflection through a horizontal axis (also called [). S0Reflection through a vertical axis (also called \). T2Reflection through the main diagonal (also called ]). U&Reflection through the anti-diagonal. VEThe dihedral group of order 8 (the symmetries of a square); that is, ' d8 = [r0, r1, r2, r3, s0, s1, s2, s3] W:The Klein four-group (the symmetries of a non-equilateral  rectangle); that is,  klein4 = [r0, r2, s0, s1] X orbit fs x is the orbit of x under the functions in fs. E.g., 6 orbit klein4 "2314" == ["1423","2314","3241","4132"] Y id = r0Z  rotate = r1[ complement = s0\  reverse = s1]  inverse = s2NOPQRSTUVWXYZ[\]NOPQRSTUVWXYZ[\]NOPQRSTUVWXYZ[\]NOPQRSTUVWXYZ[\]+Anders Claesson <anders.claesson@gmail.com>None^The 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; aThe number of  fixed points : positions i such that w[i] == i; bThe number of  inversions: pairs (i,j) such that i < j and w[i] > w[j] cThe major index is the sum of descents. dThe number of peaks : positions i such that w[i-1] < w[i] and w[i] > w[i+1]. eThe number of valleys : positions i such that w[i-1] > w[i] and w[i] < w[i+1]. fThe number of double ascents : positions i such that w[i-1] < w[i] < w[i+1]. gThe number of double descents : positions i such that w[i-1] > w[i] > w[i+1]. hThe number of left-to-right minima : positions i such that w[i] < w[j] for all j < i. iThe number of left-to-right maxima : positions i such that w[i] > w[j] for all j < i. jThe number of right-to-left minima : positions i such that w[i] < w[j] for all j > i. kThe number of right-to-left maxima : positions i such that w[i] > w[j] for all j > i. l<The first (left-most) element in the standardization. E.g., head "231" = head (fromList [1,2,0]) = 1. m<The last (right-most) element in the standardization. E.g., last "231" = last (fromList [1,2,0]) = 0. n0Length of the left-most increasing run: largest i such that  w[0] < w[1] < ... < w[i-1]. o0Length of the left-most decreasing run: largest i such that  w[0] > w[1] > ... > w[i-1]. p1Length of the right-most increasing run: largest i such that  w[n-i] < ... < w[n-2] < w[n-1]. q1Length of the right-most decreasing run: largest i such that  w[n-i] > ... > w[n-2] > w[n-1]. r 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]. s8The 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 ] ^_`abcdefghijklmnopqrs^_`abcdefghijklmnopqrs^_`abcdefghijklmnopqrs^_`abcdefghijklmnopqrsž      !"#$%&'()*+,-./0123456789 :;<  =>?@34ABCDEFGHIJKLMNO#$/0%&'()*+, -.!"12PQRSTUVWXYZ[\]^_`abcdefghijklmPnoPnpq:rstuvwxyz?{ sym-0.1.1Math.Sym.InternalMath.Sym Math.Sym.D8 Math.Sym.StatPerm0 LehmercodeunrankLehmercodefromLehmercoderandomLehmercode lehmercodessizetoListfromListact unrankPerm randomPermsymidperm revIdpermstistordisocopiesavoidersreverse complementinverserotateheadlastrminrmaxrirrdrascdesinvmajpeakvalldascddeslminlmaxlirldrexcfpcompep stackSort bubbleSort nextCUInt onesCUInt nextIntegralSetPermStPermtoVector fromVector/-/ unrankStPerm generalizepermsavoidsavsubsetsr0r1r2r3s0s1s2s3d8klein4orbitidbaseForeign.C.TypesCUIntc_onesc_next c_bubblesort c_stacksortc_epc_compc_ldrc_lirc_lmaxc_lminc_ddesc_dascc_vallc_peakc_majc_invc_fpc_excc_desc_ascc_ordiso factorial avoiders1statsortopnextones Data.MonoidmappendMonoidBitmaskperm0act'bitmasks$fBitmaskInteger$fBitmaskCUInt$fPerm[] $fPermStPerm$fMonoidStPerm $fShowStPerm