-- 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 permutation statistics.
@package sym
@version 0.9
-- | Convenience functions for dealing with arrays of CLongs.
module Data.CLongArray
-- | An array of CLongs
data CLongArray
-- | Construct an array from a list of elements.
fromList :: [Int] -> CLongArray
-- | The list of elements.
toList :: CLongArray -> [Int]
-- | Slice a CLongArray into contiguous segments of the given sizes.
-- Each segment size must be positive and they must sum to the size of
-- the array.
slice :: [Int] -> CLongArray -> [CLongArray]
-- | Like slice but without range checking.
unsafeSlice :: [Int] -> CLongArray -> [CLongArray]
-- | The size/length of the given array.
size :: CLongArray -> Int
-- | w `at` i is the value of w at i, where
-- i is in [0..size w-1].
at :: CLongArray -> Int -> Int
-- | Like at but without range checking.
unsafeAt :: CLongArray -> Int -> Int
-- | Apply a function to every element of an array and its index.
imap :: (Int -> CLong -> CLong) -> CLongArray -> CLongArray
-- | Create a new array of the given size that is initialized through an IO
-- action.
unsafeNew :: Int -> (Ptr CLong -> IO ()) -> IO CLongArray
-- | Pass a pointer to the array to an IO action; the array may not be
-- modified through the pointer.
unsafeWith :: CLongArray -> (Ptr CLong -> IO a) -> IO a
instance Ord CLongArray
instance Eq CLongArray
instance Show CLongArray
-- | Generating permutations: rank and unrank
module Data.Perm
-- | A permutation is just a CLongArray. By convention a permutation
-- of size n is understood to be a permutation of
-- [0..n-1].
type Perm = CLongArray
-- | The unique permutation length zero.
emptyperm :: Perm
-- | The unique permutation length one.
one :: Perm
-- | The identity permutation.
idperm :: Int -> Perm
-- | The reverse of the identity permutation.
ebb :: Int -> Perm
-- | Construct a permutation from a list of elements. As opposed to
-- fromList this is a safe function in the sense that the output
-- of mkPerm xs is guaranteed to be a permutation of
-- [0..length xs-1]. E.g., mkPerm "baxa" == fromList
-- [2,0,3,1].
mkPerm :: Ord a => [a] -> Perm
-- | The rank of the given permutation, where the rank is defined as in [W.
-- Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear
-- Time, Information Processing Letters, 79 (2001) 281-284].
rank :: Perm -> Integer
-- | The permutation of size n whose rank is r, where the
-- rank is defined as in [W. Myrvold and F. Ruskey, Ranking and Unranking
-- Permutations in Linear Time, Information Processing Letters, 79 (2001)
-- 281-284].
unrank :: Int -> Integer -> Perm
-- | All permutations of a given size.
perms :: Int -> [Perm]
-- | Permutation diagrams, or permutations as monads.
module Data.Permgram
-- | The purpose of this data type is to assign labels to the indices of a
-- given permutation.
type Label a = Array Int a
-- | A permgram consists of a permutation together with a label for each
-- index of the permutation.
data Permgram a
-- | The underlying permutation.
perm :: Permgram a -> Perm
-- | The assignment of labels to indices.
label :: Permgram a -> Label a
-- | The size of a permgram is the size of the underlying permutation.
size :: Permgram a -> Int
-- | Construct a permgram from an underlying permutation and a list of
-- labels.
permgram :: Perm -> [a] -> Permgram a
-- | The inverse permgram. It's obtained by mirroring the permgram in the
-- x=y diagonal.
inverse :: Permgram a -> Permgram a
instance Monad Permgram
instance Functor Permgram
instance Ord a => Ord (Permgram a)
instance Eq a => Eq (Permgram a)
instance Show a => Show (Permgram a)
module Math.Perm.Bijection
-- | The Simion-Schmidt bijection from Av(123) onto Av(132).
simionSchmidt :: Perm -> Perm
-- | The inverse of the Simion-Schmidt bijection. It is a function from
-- Av(132) to Av(123).
simionSchmidt' :: Perm -> Perm
module Math.Perm.Group
-- | The product/composition of u and v: if w = u
-- compose v then w `at ` i = v `at` (u `at` i).
compose :: Perm -> Perm -> Perm
-- | The (left) group action of Perm on itself: if w = u act
-- v then w `at ` (u `at` i) = v `at` i.
act :: Perm -> Perm -> Perm
module Math.Perm.Simple
-- | Is the permutation simple?
simple :: Perm -> Bool
module Math.Perm.Sort
-- | One pass of stack-sort.
stackSort :: Perm -> Perm
-- | One pass of bubble-sort.
bubbleSort :: Perm -> Perm
module Math.Perm.Pattern
-- | Pattern is just an alias for permutation.
type Pattern = Perm
-- | A set is represented by an increasing array of non-negative integers.
type Set = CLongArray
-- | ordiso u v m determines whether the subword in v
-- specified by m is order isomorphic to u.
ordiso :: Perm -> Perm -> Set -> Bool
-- | subsets n k is the list of subsets of [0..n-1] with
-- k elements.
subsets :: Int -> Int -> [Set]
-- | copies p w is the list of sets that represent copies of
-- p in w.
copiesOf :: Pattern -> Perm -> [Set]
-- | w contains p is a predicate determining if w
-- contains the pattern p.
contains :: Perm -> Pattern -> Bool
-- | w avoids p is a predicate determining if w
-- avoids the pattern p.
avoids :: Perm -> Pattern -> Bool
-- | w avoidsAll ps is a predicate determining if
-- w avoids the patterns ps.
avoidsAll :: Perm -> [Pattern] -> Bool
-- | avoiders ps ws is the list of permutations in ws
-- avoiding the patterns in ps.
avoiders :: [Pattern] -> [Perm] -> [Perm]
-- | The set of minimal elements with respect to containment.
minima :: [Pattern] -> [Pattern]
-- | The set of maximal elements with respect to containment.
maxima :: [Pattern] -> [Pattern]
-- | 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 -> Int) -> Pattern -> Int
module Math.Perm.D8
-- | Ration by 0 degrees, i.e. the identity map.
r0 :: Perm -> Perm
-- | Ration by 90 degrees clockwise.
r1 :: Perm -> Perm
-- | Ration by 2*90 = 180 degrees clockwise.
r2 :: Perm -> Perm
-- | Ration by 3*90 = 270 degrees clockwise.
r3 :: Perm -> Perm
-- | Reflection through a horizontal axis (also called complement).
s0 :: Perm -> Perm
-- | Reflection through a vertical axis (also called reverse).
s1 :: Perm -> Perm
-- | Reflection through the main diagonal (also called inverse).
s2 :: Perm -> Perm
-- | Reflection through the anti-diagonal.
s3 :: Perm -> Perm
-- | The dihedral group of order 8 (the symmetries of a square); that is,
--
--
-- d8 = [r0, r1, r2, r3, s0, s1, s2, s3]
--
d8 :: [Perm -> Perm]
-- | The Klein four-group (the symmetries of a non-equilateral rectangle);
-- that is,
--
--
-- klein4 = [r0, r2, s0, s1]
--
klein4 :: [Perm -> Perm]
-- | 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 -> Perm] -> Perm -> [Perm]
-- | symmetryClasses fs xs is the list of equivalence classes
-- under the action of the group of functions fs.
symmetryClasses :: [Perm -> Perm] -> [Perm] -> [[Perm]]
-- | Symmetry classes with respect to D8.
d8Classes :: [Perm] -> [[Perm]]
-- | Symmetry classes with respect to Klein4
klein4Classes :: [Perm] -> [[Perm]]
-- |
-- rotate = r1 = inverse . reverse
--
rotate :: Perm -> Perm
-- | The complement of the given permutation: if v = complement u
-- then v `at` i = n - 1 - u `at` i.
complement :: Perm -> Perm
-- | The reverse of the given permutation: if v = reverse u then
-- v `at` i = u `at` (n-1-i).
reverse :: Perm -> Perm
-- | The group theoretical inverse: if v = inverse u then v
-- `at` (u `at` i) = i.
inverse :: Perm -> Perm
-- | Components of permutations.
module Math.Perm.Component
-- | The list of (plus) components.
components :: Perm -> [Perm]
-- | The list of skew components, also called minus components.
skewComponents :: Perm -> [Perm]
-- | For each position, left-to-right, records the largest value seen thus
-- far.
leftMaxima :: Perm -> [Int]
-- | For each position, left-to-right, records the smallest value seen thus
-- far.
leftMinima :: Perm -> [Int]
-- | For each position, right-to-left, records the largest value
-- seen thus far.
rightMaxima :: Perm -> [Int]
-- | For each position, right-to-left, records the smallest value
-- seen thus far.
rightMinima :: Perm -> [Int]
-- | Sum, skew sum, etc
module Math.Perm.Constructions
-- | The direct sum of two permutations.
(/+/) :: Perm -> Perm -> Perm
-- | The skew sum of two permutations.
(\-\) :: Perm -> Perm -> Perm
-- | The direct sum of a list of permutations.
directSum :: [Perm] -> Perm
-- | The skew sum of a list of permutations.
skewSum :: [Perm] -> Perm
-- | 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 (mkPerm "12") [u,v]
-- u \-\ v == inflate (mkPerm "21") [u,v]
--
inflate :: Perm -> [Perm] -> Perm
module Math.Perm.Class
-- | The class of increasing permutations.
inc :: Int -> [Perm]
-- | The class of decreasing permutations.
dec :: Int -> [Perm]
-- | Av(1)
av1 :: Int -> [Perm]
-- | Av(12)
av12 :: Int -> [Perm]
-- | Av(21)
av21 :: Int -> [Perm]
-- | Av(123)
av123 :: Int -> [Perm]
-- | Av(132)
av132 :: Int -> [Perm]
-- | Av(213)
av213 :: Int -> [Perm]
-- | Av(231); also know as the stack sortable permutations.
av231 :: Int -> [Perm]
-- | Av(312)
av312 :: Int -> [Perm]
-- | Av(321)
av321 :: Int -> [Perm]
-- | Av(1243)
av1243 :: Int -> [Perm]
-- | Av(1324)
av1324 :: Int -> [Perm]
-- | Av(2134)
av2134 :: Int -> [Perm]
-- | Av(s) where s is a string of one or more patterns, using space as a
-- seperator.
av :: String -> Int -> [Perm]
-- | 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 :: Int -> [Perm]
-- | 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 :: Int -> [Perm]
-- | 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 :: Int -> [Perm]
-- | 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 :: Int -> [Perm]
-- | The union of vee, caret, gt and lt.
wedges :: Int -> [Perm]
-- | The class of separable permutations; it is identical to Av(2413,3142).
separables :: Int -> [Perm]
-- | The class of layered permutations with k layers.
kLayered :: Int -> Int -> [Perm]
-- | The class of layered permutations.
layered :: Int -> [Perm]
-- | The class of Fibonacci permutations with k layers. A
-- Fibonacci permutation is a layered permutation whose layers are
-- all of size 1 or 2.
kFibonacci :: Int -> Int -> [Perm]
-- | The class of Fibonacci permutations. A Fibonacci permutation is
-- a layered permutation whose layers are all of size 1 or 2.
fibonacci :: Int -> [Perm]
-- | A meta module collecting all Perm-modules, except those that are best
-- imported "qualified".
module Math.Perm
-- | Common permutation statistics. To avoid name clashes this module is
-- best imported qualified; e.g.
--
--
-- import qualified Math.Perm.Stat as S
--
module Math.Perm.Stat
-- | The number of ascents. An ascent in w is an index
-- i such that w[i] < w[i+1].
asc :: Perm -> Int
-- | The number of descents. A descent in w is an index
-- i such that w[i] > w[i+1].
des :: Perm -> Int
-- | The number of excedances: positions i such that
-- w[i] > i.
exc :: Perm -> Int
-- | The number of fixed points: positions i such that
-- w[i] == i.
fp :: Perm -> Int
-- | The number of strong fixed points (also called splitters):
-- positions i such that w[j] < i for j <
-- i and w[j] > i for j > i.
sfp :: Perm -> Int
-- | The number of cycles: orbits of the permutation when viewed as
-- a function.
cyc :: Perm -> Int
-- | The number of inversions: pairs (i,j) such that i
-- < j and w[i] > w[j].
inv :: Perm -> Int
-- | The major index is the sum of descents.
maj :: Perm -> Int
-- | The co-major index is the sum of descents.
comaj :: Perm -> Int
-- | The number of peaks: positions i such that w[i-1]
-- < w[i] and w[i] > w[i+1].
peak :: Perm -> Int
-- | The number of valleys: positions i such that
-- w[i-1] > w[i] and w[i] < w[i+1].
vall :: Perm -> Int
-- | The number of double ascents: positions i such that
-- w[i-1] < w[i] < w[i+1].
dasc :: Perm -> Int
-- | The number of double descents: positions i such that
-- w[i-1] > w[i] > w[i+1].
ddes :: Perm -> Int
-- | The number of left-to-right minima: positions i such
-- that w[i] < w[j] for all j < i.
lmin :: Perm -> Int
-- | The number of left-to-right maxima: positions i such
-- that w[i] > w[j] for all j < i.
lmax :: Perm -> Int
-- | The number of right-to-left minima: positions i such
-- that w[i] < w[j] for all j > i.
rmin :: Perm -> Int
-- | The number of right-to-left maxima: positions i such
-- that w[i] > w[j] for all j > i.
rmax :: Perm -> Int
-- | The first (left-most) element in the standardization. E.g., head
-- "231" = head (fromList [1,2,0]) = 1.
head :: Perm -> Int
-- | The last (right-most) element in the standardization. E.g., last
-- "231" = last (fromList [1,2,0]) = 0.
last :: Perm -> Int
-- | Length of the left-most increasing run: largest i such that
-- w[0] < w[1] < ... < w[i-1].
lir :: Perm -> Int
-- | Length of the left-most decreasing run: largest i such that
-- w[0] > w[1] > ... > w[i-1].
ldr :: Perm -> Int
-- | Length of the right-most increasing run: largest i such that
-- w[n-i] < ... < w[n-2] < w[n-1].
rir :: Perm -> Int
-- | Length of the right-most decreasing run: largest i such that
-- w[n-i] > ... > w[n-2] > w[n-1].
rdr :: Perm -> 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 -> 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 -> 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 -> Int
-- | The dimension of a permutation is defined as the largest
-- non-fixed-point, or zero if all points are fixed.
dim :: Perm -> 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 -> 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 -> Int
module Math.Sym
-- | 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 => Permutation a where size = size . st inverse = unst . inverse . st ordiso u v = u == st v unst w = w `act` idperm (size w)
st :: Permutation a => a -> Perm
act :: Permutation a => Perm -> a -> a
size :: Permutation a => a -> Int
idperm :: Permutation a => Int -> a
inverse :: Permutation a => a -> a
ordiso :: Permutation a => Perm -> a -> Bool
unst :: (Permutation a, Permutation a) => Perm -> a
-- | The list of all permutations of the given size.
perms :: Permutation a => Int -> [a]
-- | Lifts a function on Perms to one on any permutations.
lift :: Permutation a => (Perm -> Perm) -> a -> a
-- | Like lift but for functions of two variables.
lift2 :: Permutation a => (Perm -> Perm -> Perm) -> a -> a -> a
instance Permutation String
instance Permutation Perm