-- 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.3 -- | 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 -- | act u v is the permutation w defined by w(u(i)) = -- v(i). act :: 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 right-to-left minima. rmin :: Perm0 -> Int -- | The number of right-to-left 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 -- | 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 list of values of left-to-right minima lminValues :: Perm0 -> Vector Int -- | The list of indices of left-to-right minima lminIndices :: 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 -- | 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 vector. toVector :: StPerm -> Vector Int -- | Convert 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. fromVector :: Vector Int -> 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 skew sum of two permutations. (A definition of the -- direct sum is provided by mappend of the Monoid -- instance for StPerm.) (/-/) :: StPerm -> StPerm -> StPerm -- | unrankStPerm n rank is the rank-th (Myrvold & -- Ruskey) permutation of [0..n-1]. E.g., -- -- 
--   unrankStPerm 16 19028390 == fromList [6,15,4,11,7,8,9,2,5,0,10,3,12,13,14,1]
--
unrankStPerm :: Int -> Integer -> 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 implementations of -- size and neutralize can be somewhat slow, so you may -- want to implement them as well. class Perm a where size = size . st neutralize = idperm . size inverse u = inverse (st u) `act` neutralize u ordiso u v = u == st v st :: Perm a => a -> StPerm act :: Perm a => StPerm -> a -> a size :: Perm a => a -> Int idperm :: Perm a => Int -> a neutralize :: Perm a => a -> a inverse :: Perm a => a -> a ordiso :: Perm a => StPerm -> a -> Bool -- | Generalize a function on StPerm 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. generalize :: Perm a => (StPerm -> StPerm) -> 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 -- | copiesOf p w 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]]
--
copiesOf :: Perm a => StPerm -> a -> [Set] -- | avoids w ps is a predicate determining if w avoids -- the patterns ps. avoids :: Perm a => a -> [StPerm] -> Bool -- | avoiders 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. avoiders :: Perm a => [StPerm] -> [a] -> [a] -- | av ps n is the list of permutations of [0..n-1] -- avoiding the patterns ps. E.g., -- -- 
--   map (length . av [st "132", st "321"]) [1..8] == [1,2,4,7,11,16,22,29]
--
av :: [StPerm] -> Int -> [StPerm] -- | Delete the element at a given position del :: Perm a => Int -> a -> a -- | The list of all single point deletions shadow :: (Ord a, Perm a) => a -> [a] -- | Insert a new largest element at the given position ext :: Perm a => Int -> a -> a -- | The list of all single point extensions coshadow :: (Ord a, Perm a) => a -> [a] -- | 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 Bitmask Integer instance Bitmask CUInt instance Perm [Int] instance Perm String 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 functions in -- fs. E.g., -- -- 
--   orbit klein4 "2314" == ["1423","2314","3241","4132"]
--
orbit :: Ord a => Perm a => [a -> 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 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 list of values of left-to-right minima lminValues :: Perm a => a -> [Int] -- | The list of indices of left-to-right minima lminIndices :: Perm a => a -> [Int]