-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Permutations, patterns, and statistics -- -- Definitions for permutations with an emphasis on permutation patterns -- and statistics. -- -- @package sym @version 0.8 -- | An internal module used by the sym package. -- -- A Lehmercode is a vector of integers w such w!i <= -- length w - 1 - i for each i in [0..length w - -- 1]; such a vector encodes a permutation. This module implements -- O(n) algorithms for unranking Lehmercodes and permutations; the -- algorithms are due to W. Myrvold and F. Ruskey [Ranking and Unranking -- Permutations in Linear Time, Information Processing Letters, 79 (2001) -- 281-284]. -- -- In addition, this module implements sorting operators, the symmetries -- in D8 acting on permutations, as well as most of the common -- permutation statistics. module Math.Sym.Internal -- | A Lehmercode is a vector of integers w such w!i <= -- length w - 1 - i for each i in [0..length w - -- 1]. type Lehmercode = Vector Int -- | By convention, a member of Perm0 is a permutation of some -- finite subset of [0..]. type Perm0 = Vector Int -- | unrankLehmercode n rank is the rank-th Lehmercode of -- length n. unrankLehmercode :: Int -> Integer -> Lehmercode -- | Build a permutation from its Lehmercode. fromLehmercode :: Lehmercode -> Perm0 -- | A random Lehmercode of the given length. randomLehmercode :: Int -> IO Lehmercode -- | The list of Lehmercodes of a given length. lehmercodes :: Int -> [Lehmercode] -- | The size of a permutation; the number of elements. size :: Perm0 -> Int -- | The list of images of a permutation. toList :: Perm0 -> [Int] -- | Make a permutation from a list of images. fromList :: [Int] -> Perm0 -- | u act v is the permutation w defined by -- w(u(i)) = v(i). act :: Perm0 -> Perm0 -> Perm0 -- | inflate w vs is the inflation of w by -- vs. inflate :: Perm0 -> [Perm0] -> Perm0 -- | unrankPerm n rank is the rank-th (Myrvold & -- Ruskey) permutation of length n. unrankPerm :: Int -> Integer -> Perm0 -- | A random permutation of the given length. randomPerm :: Int -> IO Perm0 -- | sym n is the list of permutations of [0..n-1] (the -- symmetric group). sym :: Int -> [Perm0] -- | The identity permutation of the given length. idperm :: Int -> Perm0 -- | The reverse of the identity permutation. revIdperm :: Int -> Perm0 -- | 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>. sti :: Perm0 -> Perm0 -- | The standardization map. st :: Perm0 -> Perm0 -- | ordiso u v m determines whether the subword in v -- specified by m is order isomorphic to u. ordiso :: Perm0 -> Perm0 -> Vector Int -> Bool -- | simple w determines whether w is simple simple :: Perm0 -> Bool -- | copies subsets p w is the list of bitmasks that represent -- copies of p in w. copies :: (Int -> Int -> [Vector Int]) -> Perm0 -> Perm0 -> [Vector Int] -- | avoiders subsets st ps ws is the list of permutations in -- ws avoiding the patterns in ps. avoiders :: (Int -> Int -> [Vector Int]) -> (a -> Perm0) -> [Perm0] -> [a] -> [a] -- | reverse <a_1,...,a_n> == <a_n,,...,a_1>. E.g., -- reverse <9,3,7,2> == <2,7,3,9>. reverse :: Perm0 -> Perm0 -- | 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>. complement :: Perm0 -> Perm0 -- | inverse w is the group theoretical inverse of w. -- E.g., inverse <1,2,0> == <2,0,1>. inverse :: Perm0 -> Perm0 -- | The clockwise rotatation through 90 degrees. E.g., rotate -- <1,0,2> == <1,2,0>. rotate :: Perm0 -> Perm0 -- | The number of ascents. asc :: Perm0 -> Int -- | The number of descents. des :: Perm0 -> Int -- | The number of excedances. exc :: Perm0 -> Int -- | The number of fixed points. fp :: Perm0 -> Int -- | The number of cycles. cyc :: Perm0 -> Int -- | The number of inversions. inv :: Perm0 -> Int -- | The major index. maj :: Perm0 -> Int -- | The co-major index. comaj :: Perm0 -> Int -- | The number of peaks. peak :: Perm0 -> Int -- | The number of valleys. vall :: Perm0 -> Int -- | The number of double ascents. dasc :: Perm0 -> Int -- | The number of double descents. ddes :: Perm0 -> Int -- | The number of left-to-right minima. lmin :: Perm0 -> Int -- | The number of left-to-right maxima. lmax :: Perm0 -> Int -- | The number of left-to-right minima. rmin :: Perm0 -> Int -- | The number of left-to-right maxima. rmax :: Perm0 -> Int -- | First (left-most) value of a permutation. head :: Perm0 -> Int -- | Last (right-most) value of a permutation. last :: Perm0 -> Int -- | The left-most increasing run. lir :: Perm0 -> Int -- | The left-most decreasing run. ldr :: Perm0 -> Int -- | The right-most increasing run. rir :: Perm0 -> Int -- | The right-most decreasing run. rdr :: Perm0 -> Int -- | The number of components. comp :: Perm0 -> Int -- | The number of skew components. scomp :: Perm0 -> Int -- | Rank as defined by Elizalde & Pak. ep :: Perm0 -> Int -- | Dimension (largest non-fixed-point). dim :: Perm0 -> Int -- | The number of small ascents. asc0 :: Perm0 -> Int -- | The number of small descents. des0 :: Perm0 -> Int -- | The set of indices of left-to-right maxima. lMaxima :: Perm0 -> Vector Int -- | The set of indices of right-to-left maxima. rMaxima :: Perm0 -> Vector Int -- | The set of indices of components. components :: Perm0 -> Vector Int -- | One pass of stack-sort. stackSort :: Perm0 -> Perm0 -- | One pass of bubble-sort. bubbleSort :: Perm0 -> Perm0 -- | Delete the element at a given position del :: Int -> Perm0 -> Perm0 -- | The Simion-Schmidt bijection from Av(123) onto Av(132). simionSchmidt :: Perm0 -> Perm0 -- | The inverse of the Simion-Schmidt bijection. It is a function from -- Av(132) to Av(123). simionSchmidt' :: Perm0 -> Perm0 -- | onesCUInt k m gives the k smallest indices whose -- bits are set in m. onesCUInt :: CUInt -> Vector Int -- | Lexicographically, the next CUInt with the same Hamming weight. nextCUInt :: CUInt -> CUInt -- | Lexicographically, the next integral number with the same Hamming -- weight. nextIntegral :: (Integral a, Bits a) => a -> a -- | Provides an efficient definition of standard permutations, -- StPerm, together with an abstract class, Perm, whose -- functionality is largely inherited from StPerm using a group -- action and the standardization map. module Math.Sym -- | By a standard permutation we shall mean a permutations of -- [0..k-1]. data StPerm -- | Convert a standard permutation to a list. toList :: StPerm -> [Int] -- | 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. fromList :: [Int] -> StPerm -- | The list of standard permutations of the given size (the symmetric -- group). E.g., -- -- 
--   sym 2 == [fromList [0,1], fromList [1,0]]
--
sym :: Int -> [StPerm] -- | The class of permutations. Minimal complete definition: st, -- act and idperm. The default implementation of -- size can be somewhat slow, so you may want to implement it as -- well. class Ord a => Perm a where size = size . st inverse = unst . inverse . st ordiso u v = u == st v unstn n w = w `act` idperm n unst w = unstn (size w) w st :: Perm a => a -> StPerm act :: Perm a => StPerm -> a -> a size :: Perm a => a -> Int idperm :: Perm a => Int -> a inverse :: Perm a => a -> a ordiso :: Perm a => StPerm -> a -> Bool unstn :: Perm a => Int -> StPerm -> a unst :: (Perm a, Perm a) => StPerm -> a -- | A String viewed as a permutation of its characters. The alphabet is -- ordered as -- -- 
--   ['1'..'9'] ++ ['A'..'Z'] ++ ['a'..]
--
newtype CharPerm CharPerm :: String -> CharPerm chars :: CharPerm -> String -- | A list of integers viewed as a permutation. newtype IntPerm IntPerm :: [Int] -> IntPerm ints :: IntPerm -> [Int] -- | Type alias for IntMap Int. This can be thought of as a -- permutations in two line notation. newtype Perm2 Perm2 :: IntMap Int -> Perm2 intmap :: Perm2 -> IntMap Int -- | The empty permutation. empty :: Perm a => a -- | The one letter permutation. one :: Perm a => a -- | Convert a permutation to a vector. toVector :: Perm a => a -> Vector Int -- | 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. fromVector :: Perm a => Vector Int -> a -- | The bijective function defined by a permutation. bijection :: Perm a => a -> Int -> Int -- | Lift a function on 'Vector Int' to a function on any permutations: -- -- 
--   lift f = fromVector . f . toVector
--
lift :: (Perm a, Perm b) => (Vector Int -> Vector Int) -> a -> b -- | Like lift but for functions of two variables lift2 :: (Perm a, Perm b, Perm c) => (Vector Int -> Vector Int -> Vector Int) -> a -> b -> c -- | Sort a list of permutations with respect to the standardization and -- remove duplicates normalize :: Perm a => [a] -> [a] -- | Cast a permutation of one type to another cast :: (Perm a, Perm b) => a -> b -- | The direct sum of two permutations. (/+/) :: Perm a => a -> a -> a -- | The direct sum of a list of permutations. dsum :: Perm a => [a] -> a -- | The skew sum of two permutations. (\-\) :: Perm a => a -> a -> a -- | The skew sum of a list of permutations. ssum :: Perm a => [a] -> a -- | 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]
--
inflate :: (Perm a, Perm b) => b -> [a] -> a -- | unrankPerm u rank is the rank-th (Myrvold & -- Ruskey) permutation of size n. E.g., -- -- 
--   unrankPerm 9 88888 == "561297843"
--
unrankPerm :: Perm a => Int -> Integer -> a -- | randomPerm n is a random permutation of size n. randomPerm :: Perm a => Int -> IO a -- | All permutations of a given size. E.g., -- -- 
--   perms 3 == ["123","213","321","132","231","312"]
--
perms :: Perm a => Int -> [a] -- | One pass of stack-sort. stackSort :: Perm a => a -> a -- | One pass of bubble-sort. bubbleSort :: Perm a => a -> a -- | All methods of the Pattern typeclass have default implementations. -- This is because any permutation can also be seen as a pattern. If you -- want to override the default implementation you should at least define -- copiesOf. class Perm a => Pattern a where copiesOf p w = copies subsets (toVector p) (toVector w) w contains p = not $ w `avoids` p w avoids p = null $ copiesOf p w w avoidsAll ps = all (w `avoids`) ps avoiders ps = filter (`avoidsAll` ps) copiesOf :: (Pattern a, Perm b) => a -> b -> [Set] contains :: (Pattern a, Perm b) => b -> a -> Bool avoids :: (Pattern a, Perm b) => b -> a -> Bool avoidsAll :: (Pattern a, Perm b) => b -> [a] -> Bool avoiders :: (Pattern a, Perm b) => [a] -> [b] -> [b] -- | stat p is the pattern p when regarded as a -- statistic/function counting copies of itself: -- -- 
--   stat p = length . copiesOf p
--
stat :: (Pattern a, Perm b) => a -> b -> Int -- | av ps n is the list of permutations of [0..n-1] -- avoiding the patterns ps. E.g., -- -- 
--   map (length . av ["132","321"]) [1..8] == [1,2,4,7,11,16,22,29]
--
av :: Pattern a => [a] -> Int -> [StPerm] -- | Like av but the return type is any set of permutations. permClass :: (Pattern a, Perm b) => [a] -> Int -> [b] -- | Delete the element at a given position del :: Perm a => Int -> a -> a -- | The list of all single point deletions shadow :: Perm a => [a] -> [a] -- | The list of permutations that are contained in at least one of the -- given permutaions downset :: Perm a => [a] -> [a] -- | 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. ext :: Perm a => Int -> Int -> a -> a -- | The list of all single point extensions coshadow :: Perm a => [a] -> [a] -- | The set of minimal elements with respect to containment. minima :: Pattern a => [a] -> [a] -- | The set of maximal elements with respect to containment. maxima :: Pattern a => [a] -> [a] -- | coeff f v is the coefficient of v when expanding the -- permutation statistic f as a sum of permutations/patterns. -- See Petter Brändén and Anders Claesson: Mesh patterns and the -- expansion of permutation statistics as sums of permutation patterns, -- The Electronic Journal of Combinatorics 18(2) (2011), -- http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p5. coeff :: Pattern a => (a -> Int) -> a -> Int -- | The set of indices of left-to-right maxima. lMaxima :: Perm a => a -> Set -- | The set of indices of left-to-right minima. lMinima :: Perm a => a -> Set -- | The set of indices of right-to-left maxima. rMaxima :: Perm a => a -> Set -- | The set of indices of right-to-left minima. rMinima :: Perm a => a -> Set -- | The set of indices of components. components :: Perm a => a -> Set -- | The set of indices of skew components. skewComponents :: Perm a => a -> Set -- | A predicate determining if a given permutation is simple. simple :: Perm a => a -> Bool -- | A set is represented by an increasing vector of non-negative integers. type Set = Vector Int -- | subsets n k is the list of subsets of [0..n-1] with -- k elements. subsets :: Int -> Int -> [Set] instance Eq StPerm instance Eq CharPerm instance Eq IntPerm instance Eq Perm2 instance Bitmask Integer instance Bitmask CUInt instance Pattern Perm2 instance Pattern IntPerm instance Pattern CharPerm instance Pattern String instance Pattern StPerm instance Perm Perm2 instance Ord Perm2 instance Show Perm2 instance Perm IntPerm instance Ord IntPerm instance Show IntPerm instance Perm String instance Perm CharPerm instance IsString CharPerm instance Ord CharPerm instance Show CharPerm instance Perm StPerm instance Monoid StPerm instance Show StPerm instance Ord StPerm -- | The dihedral group of order 8 acting on permutations. -- -- To avoid name clashes this module is best imported qualified; -- e.g. -- -- 
--   import qualified Math.Sym.D8 as D8
--
module Math.Sym.D8 -- | Ration by 0 degrees, i.e. the identity map. r0 :: Perm a => a -> a -- | Ration by 90 degrees clockwise. r1 :: Perm a => a -> a -- | Ration by 2*90 = 180 degrees clockwise. r2 :: Perm a => a -> a -- | Ration by 3*90 = 270 degrees clockwise. r3 :: Perm a => a -> a -- | Reflection through a horizontal axis (also called complement). s0 :: Perm a => a -> a -- | Reflection through a vertical axis (also called reverse). s1 :: Perm a => a -> a -- | Reflection through the main diagonal (also called inverse). s2 :: Perm a => a -> a -- | Reflection through the anti-diagonal. s3 :: Perm a => a -> a -- | The dihedral group of order 8 (the symmetries of a square); that is, -- -- 
--   d8 = [r0, r1, r2, r3, s0, s1, s2, s3]
--
d8 :: Perm a => [a -> a] -- | The Klein four-group (the symmetries of a non-equilateral rectangle); -- that is, -- -- 
--   klein4 = [r0, r2, s0, s1]
--
klein4 :: Perm a => [a -> a] -- | orbit fs x is the orbit of x under the group -- of function fs. E.g., -- -- 
--   orbit klein4 "2314" == ["1423","2314","3241","4132"]
--
orbit :: Perm a => [a -> a] -> a -> [a] -- | symmetryClasses fs xs is the list of equivalence classes -- under the action of the group of functions fs. symmetryClasses :: Perm a => [a -> a] -> [a] -> [[a]] -- | Symmetry classes with respect to D8. d8Classes :: Perm a => [a] -> [[a]] -- | Symmetry classes with respect to Klein4 klein4Classes :: Perm a => [a] -> [[a]] -- | 
--   id = r0
--
id :: Perm a => a -> a -- | 
--   rotate = r1
--
rotate :: Perm a => a -> a -- | 
--   complement = s0
--
complement :: Perm a => a -> a -- | 
--   reverse = s1
--
reverse :: Perm a => a -> a -- | 
--   inverse = s2
--
inverse :: Perm a => a -> a -- | Common permutation statistics. Please contact the maintainer if you -- feel that there is a statistic that is missing; even better, send a -- patch or make a pull request. -- -- To avoid name clashes this module is best imported qualified; -- e.g. -- -- 
--   import qualified Math.Sym.Stat as S
--
-- -- For any permutation statistic f, below, it holds that f w -- == f (st w), and therefore the explanations below will be done on -- standard permutations for convenience. module Math.Sym.Stat -- | The number of ascents. An ascent in w is an index -- i such that w[i] < w[i+1]. asc :: Perm a => a -> Int -- | The number of descents. A descent in w is an index -- i such that w[i] > w[i+1]. des :: Perm a => a -> Int -- | The number of excedances: positions i such that -- w[i] > i. exc :: Perm a => a -> Int -- | The number of fixed points: positions i such that -- w[i] == i. fp :: Perm a => a -> Int -- | The number of cycles: orbits of the permutation when viewed as -- a function. cyc :: Perm a => a -> Int -- | The number of inversions: pairs (i,j) such that i -- < j and w[i] > w[j]. inv :: Perm a => a -> Int -- | The major index is the sum of descents. maj :: Perm a => a -> Int -- | The co-major index is the sum of descents. comaj :: Perm a => a -> Int -- | The number of peaks: positions i such that w[i-1] -- < w[i] and w[i] > w[i+1]. peak :: Perm a => a -> Int -- | The number of valleys: positions i such that -- w[i-1] > w[i] and w[i] < w[i+1]. vall :: Perm a => a -> Int -- | The number of double ascents: positions i such that -- w[i-1] < w[i] < w[i+1]. dasc :: Perm a => a -> Int -- | The number of double descents: positions i such that -- w[i-1] > w[i] > w[i+1]. ddes :: Perm a => a -> Int -- | The number of left-to-right minima: positions i such -- that w[i] < w[j] for all j < i. lmin :: Perm a => a -> Int -- | The number of left-to-right maxima: positions i such -- that w[i] > w[j] for all j < i. lmax :: Perm a => a -> Int -- | The number of right-to-left minima: positions i such -- that w[i] < w[j] for all j > i. rmin :: Perm a => a -> Int -- | The number of right-to-left maxima: positions i such -- that w[i] > w[j] for all j > i. rmax :: Perm a => a -> Int -- | The first (left-most) element in the standardization. E.g., head -- "231" = head (fromList [1,2,0]) = 1. head :: Perm a => a -> Int -- | The last (right-most) element in the standardization. E.g., last -- "231" = last (fromList [1,2,0]) = 0. last :: Perm a => a -> Int -- | Length of the left-most increasing run: largest i such that -- w[0] < w[1] < ... < w[i-1]. lir :: Perm a => a -> Int -- | Length of the left-most decreasing run: largest i such that -- w[0] > w[1] > ... > w[i-1]. ldr :: Perm a => a -> Int -- | Length of the right-most increasing run: largest i such that -- w[n-i] < ... < w[n-2] < w[n-1]. rir :: Perm a => a -> Int -- | Length of the right-most decreasing run: largest i such that -- w[n-i] > ... > w[n-2] > w[n-1]. rdr :: Perm a => a -> Int -- | 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]. comp :: Perm a => a -> Int -- | 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]. scomp :: Perm a => a -> Int -- | The rank as defined by Elizalde and Pak [Bijections for refined -- restricted permutations, J. Comb. Theory, Ser. A, 2004]: -- -- 
--   maximum [ k | k <- [0..n-1], w[i] >= k for all i < k ]
--
ep :: Perm a => a -> Int -- | The dimension of a permutation is defined as the largest -- non-fixed-point, or zero if all points are fixed. dim :: Perm a => a -> Int -- | The number of small ascents. A small ascent in w is an -- index i such that w[i] + 1 == w[i+1]. asc0 :: Perm a => a -> Int -- | The number of small descents. A small descent in w is -- an index i such that w[i] == w[i+1] + 1. des0 :: Perm a => a -> Int -- | The size of the shadow of w. That is, the number of different -- one point deletions of w. shad :: Perm a => a -> Int -- | Bijections module Math.Sym.Bijection -- | The Simion-Schmidt bijection from Av(123) onto Av(132). simionSchmidt :: Perm a => a -> a -- | The inverse of the Simion-Schmidt bijection. It is a function from -- Av(132) to Av(123). simionSchmidt' :: Perm a => a -> a -- | A permutation class is a downset in the poset of permutations ordered -- by containment. This module provides definitions of some common -- classes. module Math.Sym.Class -- | The class of increasing permutations. inc :: Perm a => Int -> [a] -- | The class of decreasing permutations. dec :: Perm a => Int -> [a] -- | Av(123). av123 :: Perm a => Int -> [a] -- | Av(132). av132 :: Perm a => Int -> [a] -- | Av(213). av213 :: Perm a => Int -> [a] -- | Av(231); also know as the stack sortable permutations. av231 :: Perm a => Int -> [a] -- | Av(312). av312 :: Perm a => Int -> [a] -- | Av(321). av321 :: Perm a => Int -> [a] -- | 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. vee :: Perm a => Int -> [a] -- | The ∧-class is Av(213, 312). It is so named because the diagram of a -- typical permutation in this class is shaped like a ∧. caret :: Perm a => Int -> [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 >. gt :: Perm a => Int -> [a] -- | The <-class is Av(213, 231). It is so named because the diagram of -- a typical permutation in this class is shaped like a <. lt :: Perm a => Int -> [a] -- | The union of vee, caret, gt and lt. wedges :: Perm a => Int -> [a] -- | The class of separable permutations; it is identical to Av(2413,3142). separables :: Perm a => Int -> [a]