-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generate and manipulate various combinatorial objects.
--
-- A collection of functions to generate, count, manipulate and visualize
-- all kinds of combinatorial objects like partitions, compositions,
-- trees, permutations, braids, Young tableaux, and so on.
@package combinat
@version 0.2.8.2
-- | Vector partitions. See:
--
--
-- - Donald E. Knuth: The Art of Computer Programming, vol 4,
-- pre-fascicle 3B.
--
module Math.Combinat.Partitions.Vector
-- | Integer vectors. The indexing starts from 1.
type IntVector = UArray Int Int
-- | Vector partitions. Basically a synonym for fasc3B_algorithm_M.
vectorPartitions :: IntVector -> [[IntVector]]
_vectorPartitions :: [Int] -> [[[Int]]]
-- | Generates all vector partitions ("algorithm M" in Knuth). The order is
-- decreasing lexicographic.
fasc3B_algorithm_M :: [Int] -> [[IntVector]]
-- | Partitions of a multiset
module Math.Combinat.Partitions.Multiset
-- | Partitions of a multiset. Internally, this uses the vector partition
-- algorithm
partitionMultiset :: (Eq a, Ord a) => [a] -> [[[a]]]
-- | Creates graphviz .dot files from trees.
module Math.Combinat.Trees.Graphviz
type Dot = String
graphvizDotBinTree :: Show a => String -> BinTree a -> Dot
graphvizDotBinTree' :: (Show a, Show b) => String -> BinTree' a b -> Dot
-- | Generates graphviz .dot file from a forest. The first
-- argument tells whether to make the individual trees clustered
-- subgraphs; the second is the name of the graph.
graphvizDotForest :: Show a => Bool -> Bool -> String -> Forest a -> Dot
-- | Generates graphviz .dot file from a tree. The first argument
-- is the name of the graph.
graphvizDotTree :: Show a => Bool -> String -> Tree a -> Dot
-- | Prime numbers and related number theoretical stuff.
module Math.Combinat.Numbers.Primes
-- | Infinite list of primes, using the TMWE algorithm.
primes :: [Integer]
-- | A relatively simple but still quite fast implementation of list of
-- primes. By Will Ness
-- http://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html
primesSimple :: [Integer]
-- | List of primes, using tree merge with wheel. Code by Will Ness.
primesTMWE :: [Integer]
-- | Groups integer factors. Example: from [2,2,2,3,3,5] we produce
-- [(2,3),(3,2),(5,1)]
groupIntegerFactors :: [Integer] -> [(Integer, Int)]
-- | The naive trial division algorithm.
integerFactorsTrialDivision :: Integer -> [Integer]
-- | Largest integer k such that 2^k is smaller or equal
-- to n
integerLog2 :: Integer -> Integer
-- | Smallest integer k such that 2^k is larger or equal
-- to n
ceilingLog2 :: Integer -> Integer
isSquare :: Integer -> Bool
-- | Integer square root (largest integer whose square is smaller or equal
-- to the input) using Newton's method, with a faster (for large numbers)
-- inital guess based on bit shifts.
integerSquareRoot :: Integer -> Integer
-- | Smallest integer whose square is larger or equal to the input
ceilingSquareRoot :: Integer -> Integer
-- | We also return the excess residue; that is
--
--
-- (a,r) = integerSquareRoot' n
--
--
-- means that
--
--
-- a*a + r = n
-- a*a <= n < (a+1)*(a+1)
--
integerSquareRoot' :: Integer -> (Integer, Integer)
-- | Newton's method without an initial guess. For very small numbers
-- (<10^10) it is somewhat faster than the above version.
integerSquareRootNewton' :: Integer -> (Integer, Integer)
-- | Efficient powers modulo m.
--
--
-- powerMod a k m == (a^k) `mod` m
--
powerMod :: Integer -> Integer -> Integer -> Integer
-- | Miller-Rabin Primality Test (taken from Haskell wiki). We test the
-- primality of the first argument n by using the second
-- argument a as a candidate witness. If it returs
-- False, then n is composite. If it returns
-- True, then n is either prime or composite.
--
-- A random choice between 2 and (n-2) is a good choice
-- for a.
millerRabinPrimalityTest :: Integer -> Integer -> Bool
-- | For very small numbers, we use trial division, for larger numbers, we
-- apply the Miller-Rabin primality test log4(n) times, with
-- candidate witnesses derived deterministically from n using a
-- pseudo-random sequence (which should be based on a
-- cryptographic hash function, but isn't, yet).
--
-- Thus the candidate witnesses should behave essentially like random,
-- but the resulting function is still a deterministic, pure function.
--
-- TODO: implement the hash sequence, at the moment we use Random
-- instead...
isProbablyPrime :: Integer -> Bool
-- | A more exhaustive version of isProbablyPrime, this one tests
-- candidate witnesses both the first log4(n) prime numbers and then
-- log4(n) pseudo-random numbers
isVeryProbablyPrime :: Integer -> Bool
-- | Type-level hackery.
--
-- This module is used for groups whose parameters are encoded as
-- type-level natural numbers, for example finite cyclic groups, free
-- groups, symmetric groups and braid groups.
module Math.Combinat.TypeLevel
-- | A concrete, poly-kinded proxy type
data Proxy k (t :: k) :: forall k. k -> *
Proxy :: Proxy k
proxyUndef :: Proxy a -> a
proxyOf :: a -> Proxy a
proxyOf1 :: f a -> Proxy a
proxyOf2 :: g (f a) -> Proxy a
-- | asProxyTypeOf is a type-restricted version of const. It
-- is usually used as an infix operator, and its typing forces its first
-- argument (which is usually overloaded) to have the same type as the
-- tag of the second.
asProxyTypeOf :: a -> Proxy * a -> a
asProxyTypeOf1 :: f a -> Proxy a -> f a
typeArg :: KnownNat n => f (n :: Nat) -> Integer
iTypeArg :: KnownNat n => f (n :: Nat) -> Int
-- | Hide the type parameter of a functor. Example: Some Braid
data Some f
Some :: (f n) -> Some f
-- | Uses the value inside a Some
withSome :: Some f -> (forall n. KnownNat n => f n -> a) -> a
-- | Monadic version of withSome
withSomeM :: Monad m => Some f -> (forall n. KnownNat n => f n -> m a) -> m a
-- | Given a polymorphic value, we select at run time the one specified by
-- the second argument
selectSome :: Integral int => (forall n. KnownNat n => f n) -> int -> Some f
-- | Monadic version of selectSome
selectSomeM :: forall m f int. (Integral int, Monad m) => (forall n. KnownNat n => m (f n)) -> int -> m (Some f)
-- | Combination of selectSome and withSome: we make a
-- temporary structure of the given size, but we immediately consume it.
withSelected :: Integral int => (forall n. KnownNat n => f n -> a) -> (forall n. KnownNat n => f n) -> int -> a
-- | (Half-)monadic version of withSelected
withSelectedM :: forall m f int a. (Integral int, Monad m) => (forall n. KnownNat n => f n -> a) -> (forall n. KnownNat n => m (f n)) -> int -> m a
-- | Miscellaneous helper functions
module Math.Combinat.Helper
debug :: Show a => a -> b -> b
swap :: (a, b) -> (b, a)
pairs :: [a] -> [(a, a)]
pairsWith :: (a -> a -> b) -> [a] -> [b]
sum' :: Num a => [a] -> a
equating :: Eq b => (a -> b) -> a -> a -> Bool
reverseOrdering :: Ordering -> Ordering
reverseCompare :: Ord a => a -> a -> Ordering
reverseSort :: Ord a => [a] -> [a]
groupSortBy :: (Eq b, Ord b) => (a -> b) -> [a] -> [[a]]
nubOrd :: Ord a => [a] -> [a]
isWeaklyIncreasing :: Ord a => [a] -> Bool
isStrictlyIncreasing :: Ord a => [a] -> Bool
isWeaklyDecreasing :: Ord a => [a] -> Bool
isStrictlyDecreasing :: Ord a => [a] -> Bool
-- | The boolean argument will True only for the last element
mapWithLast :: (Bool -> a -> b) -> [a] -> [b]
mapWithFirst :: (Bool -> a -> b) -> [a] -> [b]
mapWithFirstLast :: (Bool -> Bool -> a -> b) -> [a] -> [b]
-- | extend lines with spaces so that they have the same line
mkLinesUniformWidth :: [String] -> [String]
mkBlocksUniformHeight :: [[String]] -> [[String]]
mkUniformBlocks :: [[String]] -> [[String]]
hConcatLines :: [[String]] -> [String]
vConcatLines :: [[String]] -> [String]
count :: Eq a => a -> [a] -> Int
histogram :: (Eq a, Ord a) => [a] -> [(a, Int)]
fromJust :: Maybe a -> a
intToBool :: Int -> Bool
boolToInt :: Bool -> Int
nest :: Int -> (a -> a) -> a -> a
unfold1 :: (a -> Maybe a) -> a -> [a]
unfold :: (b -> (a, Maybe b)) -> b -> [a]
unfoldEither :: (b -> Either c (b, a)) -> b -> (c, [a])
unfoldM :: Monad m => (b -> m (a, Maybe b)) -> b -> m [a]
mapAccumM :: Monad m => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y])
longZipWith :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
-- | A simple random monad to make life suck less
type Rand g = RandT g Identity
runRand :: Rand g a -> g -> (a, g)
flipRunRand :: Rand s a -> s -> (s, a)
-- | The Rand monad transformer
newtype RandT g m a
RandT :: (StateT g m a) -> RandT g m a
runRandT :: RandT g m a -> g -> m (a, g)
-- | This may be occasionally useful
flipRunRandT :: Monad m => RandT s m a -> s -> m (s, a)
-- | Puts a standard-conforming random function into the monad
rand :: (g -> (a, g)) -> Rand g a
randRoll :: (RandomGen g, Random a) => Rand g a
randChoose :: (RandomGen g, Random a) => (a, a) -> Rand g a
randProxy1 :: Rand g (f n) -> Proxy n -> Rand g (f n)
instance GHC.Base.Monad m => GHC.Base.Monad (Math.Combinat.Helper.RandT g m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Math.Combinat.Helper.RandT g m)
instance GHC.Base.Functor m => GHC.Base.Functor (Math.Combinat.Helper.RandT g m)
-- | Type classes for some common properties shared by different objects
module Math.Combinat.Classes
-- | Emptyness
class CanBeEmpty a
isEmpty :: CanBeEmpty a => a -> Bool
empty :: CanBeEmpty a => a
-- | Number of parts
class HasNumberOfParts a
numberOfParts :: HasNumberOfParts a => a -> Int
class HasWidth a
width :: HasWidth a => a -> Int
class HasHeight a
height :: HasHeight a => a -> Int
-- | Weight (of partitions, tableaux, etc)
class HasWeight a
weight :: HasWeight a => a -> Int
-- | Duality (of partitions, tableaux, etc)
class HasDuality a
dual :: HasDuality a => a -> a
-- | Shape (of tableaux, skew tableaux)
class HasShape a s | a -> s
shape :: HasShape a s => a -> s
-- | Number of nodes (of trees)
class HasNumberOfNodes t
numberOfNodes :: HasNumberOfNodes t => t -> Int
-- | Number of leaves (of trees)
class HasNumberOfLeaves t
numberOfLeaves :: HasNumberOfLeaves t => t -> Int
-- | Number of cycles (of partitions)
class HasNumberOfCycles p
numberOfCycles :: HasNumberOfCycles p => p -> Int
-- | A mini-DSL for ASCII drawing of structures.
--
-- From some structures there is also Graphviz and/or diagrams
-- (http://projects.haskell.org/diagrams) visualization support
-- (the latter in the separate libray combinat-diagrams).
module Math.Combinat.ASCII
-- | The type of a (rectangular) ASCII figure. Internally it is a list of
-- lines of the same length plus the size.
--
-- Note: The Show instance is pretty-printing, so that it's convenient in
-- ghci.
data ASCII
ASCII :: (Int, Int) -> [String] -> ASCII
[asciiSize] :: ASCII -> (Int, Int)
[asciiLines] :: ASCII -> [String]
-- | A type class to have a simple way to draw things
class DrawASCII a
ascii :: DrawASCII a => a -> ASCII
-- | An empty (0x0) rectangle
emptyRect :: ASCII
asciiXSize :: ASCII -> Int
asciiYSize :: ASCII -> Int
asciiString :: ASCII -> String
printASCII :: ASCII -> IO ()
asciiFromLines :: [String] -> ASCII
asciiFromString :: String -> ASCII
-- | Horizontal alignment
data HAlign
HLeft :: HAlign
HCenter :: HAlign
HRight :: HAlign
-- | Vertical alignment
data VAlign
VTop :: VAlign
VCenter :: VAlign
VBottom :: VAlign
data Alignment
Align :: HAlign -> VAlign -> Alignment
-- | Horizontal separator
data HSep
-- | empty separator
HSepEmpty :: HSep
-- | n spaces
HSepSpaces :: Int -> HSep
-- | some custom string, eg. " | "
HSepString :: String -> HSep
hSepSize :: HSep -> Int
hSepString :: HSep -> String
-- | Vertical separator
data VSep
-- | empty separator
VSepEmpty :: VSep
-- | n spaces
VSepSpaces :: Int -> VSep
-- | some custom list of characters, eg. " - " (the characters are
-- interpreted as below each other)
VSepString :: [Char] -> VSep
vSepSize :: VSep -> Int
vSepString :: VSep -> [Char]
-- | Horizontal append, centrally aligned, no separation.
(|||) :: ASCII -> ASCII -> ASCII
-- | Vertical append, centrally aligned, no separation.
(===) :: ASCII -> ASCII -> ASCII
-- | Horizontal concatenation, top-aligned, no separation
hCatTop :: [ASCII] -> ASCII
-- | Horizontal concatenation, bottom-aligned, no separation
hCatBot :: [ASCII] -> ASCII
-- | Vertical concatenation, left-aligned, no separation
vCatLeft :: [ASCII] -> ASCII
-- | Vertical concatenation, right-aligned, no separation
vCatRight :: [ASCII] -> ASCII
-- | General horizontal concatenation
hCatWith :: VAlign -> HSep -> [ASCII] -> ASCII
-- | General vertical concatenation
vCatWith :: HAlign -> VSep -> [ASCII] -> ASCII
-- | Horizontally pads with the given number of spaces, on both sides
hPad :: Int -> ASCII -> ASCII
-- | Vertically pads with the given number of empty lines, on both sides
vPad :: Int -> ASCII -> ASCII
-- | Pads by single empty lines vertically and two spaces horizontally
pad :: ASCII -> ASCII
-- | Extends an ASCII figure with spaces horizontally to the given width.
-- Note: the alignment is the alignment of the original picture in the
-- new bigger picture!
hExtendTo :: HAlign -> Int -> ASCII -> ASCII
-- | Extends an ASCII figure with spaces vertically to the given height.
-- Note: the alignment is the alignment of the original picture in the
-- new bigger picture!
vExtendTo :: VAlign -> Int -> ASCII -> ASCII
-- | Extend horizontally with the given number of spaces.
hExtendWith :: HAlign -> Int -> ASCII -> ASCII
-- | Extend vertically with the given number of empty lines.
vExtendWith :: VAlign -> Int -> ASCII -> ASCII
-- | Horizontal indentation
hIndent :: Int -> ASCII -> ASCII
-- | Vertical indentation
vIndent :: Int -> ASCII -> ASCII
-- | Cuts the given number of columns from the picture. The alignment is
-- the alignment of the picture, not the cuts.
--
-- This should be the (left) inverse of hExtendWith.
hCut :: HAlign -> Int -> ASCII -> ASCII
-- | Cuts the given number of rows from the picture. The alignment is the
-- alignment of the picture, not the cuts.
--
-- This should be the (left) inverse of vExtendWith.
vCut :: VAlign -> Int -> ASCII -> ASCII
-- | Pastes the first ASCII graphics onto the second, keeping the second
-- one's dimension (that is, overlapping parts of the first one are
-- ignored). The offset is relative to the top-left corner of the second
-- picture. Spaces at treated as transparent.
--
-- Example:
--
--
-- tabulate (HCenter,VCenter) (HSepSpaces 2, VSepSpaces 1)
-- [ [ caption (show (x,y)) $
-- pasteOnto (x,y) (filledBox '@' (4,3)) (asciiBox (7,5))
-- | x <- [-4..7] ]
-- | y <- [-3..5] ]
--
pasteOnto :: (Int, Int) -> ASCII -> ASCII -> ASCII
-- | Pastes the first ASCII graphics onto the second, keeping the second
-- one's dimension. The first argument specifies the transparency
-- condition (on the first picture). The offset is relative to the
-- top-left corner of the second picture.
pasteOnto' :: (Char -> Bool) -> (Int, Int) -> ASCII -> ASCII -> ASCII
-- | A version of pasteOnto where we can specify the corner of the
-- second picture to which the offset is relative:
--
--
-- pasteOntoRel (HLeft,VTop) == pasteOnto
--
pasteOntoRel :: (HAlign, VAlign) -> (Int, Int) -> ASCII -> ASCII -> ASCII
pasteOntoRel' :: (Char -> Bool) -> (HAlign, VAlign) -> (Int, Int) -> ASCII -> ASCII -> ASCII
-- | Tabulates the given matrix of pictures. Example:
--
--
-- tabulate (HCenter, VCenter) (HSepSpaces 2, VSepSpaces 1)
-- [ [ asciiFromLines [ "x=" ++ show x , "y=" ++ show y ] | x<-[7..13] ]
-- | y<-[98..102] ]
--
tabulate :: (HAlign, VAlign) -> (HSep, VSep) -> [[ASCII]] -> ASCII
-- | Order of elements in a matrix
data MatrixOrder
RowMajor :: MatrixOrder
ColMajor :: MatrixOrder
-- | Automatically tabulates ASCII rectangles.
autoTabulate :: MatrixOrder -> Either Int Int -> [ASCII] -> ASCII
-- | Adds a caption to the bottom, with default settings.
caption :: String -> ASCII -> ASCII
-- | Adds a caption to the bottom. The Bool flag specifies whether
-- to add an empty between the caption and the figure
caption' :: Bool -> HAlign -> String -> ASCII -> ASCII
-- | An ASCII border box of the given size
asciiBox :: (Int, Int) -> ASCII
-- | An "rounded" ASCII border box of the given size
roundedAsciiBox :: (Int, Int) -> ASCII
-- | A box simply filled with the given character
filledBox :: Char -> (Int, Int) -> ASCII
-- | A box of spaces
transparentBox :: (Int, Int) -> ASCII
-- | An integer
asciiNumber :: Int -> ASCII
asciiShow :: Show a => a -> ASCII
instance GHC.Read.Read Math.Combinat.ASCII.MatrixOrder
instance GHC.Show.Show Math.Combinat.ASCII.MatrixOrder
instance GHC.Classes.Ord Math.Combinat.ASCII.MatrixOrder
instance GHC.Classes.Eq Math.Combinat.ASCII.MatrixOrder
instance GHC.Show.Show Math.Combinat.ASCII.VSep
instance GHC.Show.Show Math.Combinat.ASCII.HSep
instance GHC.Show.Show Math.Combinat.ASCII.VAlign
instance GHC.Classes.Eq Math.Combinat.ASCII.VAlign
instance GHC.Show.Show Math.Combinat.ASCII.HAlign
instance GHC.Classes.Eq Math.Combinat.ASCII.HAlign
instance GHC.Show.Show Math.Combinat.ASCII.ASCII
-- | Tuples.
module Math.Combinat.Tuples
-- | "Tuples" fitting into a give shape. The order is lexicographic, that
-- is,
--
--
-- sort ts == ts where ts = tuples' shape
--
--
-- Example:
--
--
-- tuples' [2,3] =
-- [[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]]
--
tuples' :: [Int] -> [[Int]]
-- | positive "tuples" fitting into a give shape.
tuples1' :: [Int] -> [[Int]]
-- | # = \prod_i (m_i + 1)
countTuples' :: [Int] -> Integer
-- | # = \prod_i m_i
countTuples1' :: [Int] -> Integer
tuples :: Int -> Int -> [[Int]]
tuples1 :: Int -> Int -> [[Int]]
-- | # = (m+1) ^ len
countTuples :: Int -> Int -> Integer
-- | # = m ^ len
countTuples1 :: Int -> Int -> Integer
binaryTuples :: Int -> [[Bool]]
-- | Signs
module Math.Combinat.Sign
data Sign
Plus :: Sign
Minus :: Sign
isPlus :: Sign -> Bool
isMinus :: Sign -> Bool
-- | +1 or -1
signValue :: Num a => Sign -> a
-- | Negate the second argument if the first is Minus
signed :: Num a => Sign -> a -> a
-- | Plus if even, Minus if odd
paritySign :: Integral a => a -> Sign
-- |
-- (-1)^k
--
paritySignValue :: Integral a => a -> Integer
-- | Negate the second argument if the first is odd
negateIfOdd :: (Integral a, Num b) => a -> b -> b
oppositeSign :: Sign -> Sign
mulSign :: Sign -> Sign -> Sign
productOfSigns :: [Sign] -> Sign
instance GHC.Read.Read Math.Combinat.Sign.Sign
instance GHC.Show.Show Math.Combinat.Sign.Sign
instance GHC.Classes.Ord Math.Combinat.Sign.Sign
instance GHC.Classes.Eq Math.Combinat.Sign.Sign
instance GHC.Base.Monoid Math.Combinat.Sign.Sign
instance System.Random.Random Math.Combinat.Sign.Sign
-- | A few important number sequences.
--
-- See the "On-Line Encyclopedia of Integer Sequences",
-- https://oeis.org .
module Math.Combinat.Numbers
-- | A000142.
factorial :: Integral a => a -> Integer
-- | A006882.
doubleFactorial :: Integral a => a -> Integer
-- | A007318. Note: This is zero for n<0 or k<0;
-- see also signedBinomial below.
binomial :: Integral a => a -> a -> Integer
-- | The extension of the binomial function to negative inputs. This should
-- satisfy the following properties:
--
--
-- for n,k >=0 : signedBinomial n k == binomial n k
-- for any n,k : signedBinomial n k == signedBinomial n (n-k)
-- for k >= 0 : signedBinomial (-n) k == (-1)^k * signedBinomial (n+k-1) k
--
--
-- Note: This is compatible with Mathematica's Binomial
-- function.
signedBinomial :: Int -> Int -> Integer
-- | A given row of the Pascal triangle; equivalent to a sequence of
-- binomial numbers, but much more efficient. You can also left-fold over
-- it.
--
--
-- pascalRow n == [ binomial n k | k<-[0..n] ]
--
pascalRow :: Integral a => a -> [Integer]
multinomial :: Integral a => [a] -> Integer
-- | Catalan numbers. OEIS:A000108.
catalan :: Integral a => a -> Integer
-- | Catalan's triangle. OEIS:A009766. Note:
--
--
-- catalanTriangle n n == catalan n
-- catalanTriangle n k == countStandardYoungTableaux (toPartition [n,k])
--
catalanTriangle :: Integral a => a -> a -> Integer
-- | Rows of (signed) Stirling numbers of the first kind. OEIS:A008275.
-- Coefficients of the polinomial (x-1)*(x-2)*...*(x-n+1). This
-- function uses the recursion formula.
signedStirling1stArray :: Integral a => a -> Array Int Integer
-- | (Signed) Stirling numbers of the first kind. OEIS:A008275. This
-- function uses signedStirling1stArray, so it shouldn't be used
-- to compute many Stirling numbers.
--
-- Argument order: signedStirling1st n k
signedStirling1st :: Integral a => a -> a -> Integer
-- | (Unsigned) Stirling numbers of the first kind. See
-- signedStirling1st.
unsignedStirling1st :: Integral a => a -> a -> Integer
-- | Stirling numbers of the second kind. OEIS:A008277. This function uses
-- an explicit formula.
--
-- Argument order: stirling2nd n k
stirling2nd :: Integral a => a -> a -> Integer
-- | Bernoulli numbers. bernoulli 1 == -1%2 and bernoulli k ==
-- 0 for k>2 and odd. This function uses the formula
-- involving Stirling numbers of the second kind. Numerators: A027641,
-- denominators: A027642.
bernoulli :: Integral a => a -> Rational
-- | Bell numbers (Sloane's A000110) from B(0) up to B(n). B(0)=B(1)=1,
-- B(2)=2, etc.
--
-- The Bell numbers count the number of set partitions of a set of
-- size n
--
-- See http://en.wikipedia.org/wiki/Bell_number
bellNumbersArray :: Integral a => a -> Array Int Integer
-- | The n-th Bell number B(n), using the Stirling numbers of the second
-- kind. This may be slower than using bellNumbersArray.
bellNumber :: Integral a => a -> Integer
-- | Subsets.
module Math.Combinat.Sets
-- | choose_ k n returns all possible ways of choosing k
-- disjoint elements from [1..n]
--
--
-- choose_ k n == choose k [1..n]
--
choose_ :: Int -> Int -> [[Int]]
-- | All possible ways to choose k elements from a list, without
-- repetitions. "Antisymmetric power" for lists. Synonym for
-- kSublists.
choose :: Int -> [a] -> [[a]]
-- | A version of choose which also returns the complementer sets.
--
--
-- choose k = map fst . choose' k
--
choose' :: Int -> [a] -> [([a], [a])]
-- | Another variation of choose'. This satisfies
--
--
-- choose'' k == map (\(xs,ys) -> (map fst xs, map snd ys)) . choose' k
--
choose'' :: Int -> [(a, b)] -> [([a], [b])]
-- | Another variation on choose which tags the elements based on
-- whether they are part of the selected subset (Right) or not
-- (Left):
--
--
-- choose k = map rights . chooseTagged k
--
chooseTagged :: Int -> [a] -> [[Either a a]]
-- | All possible ways to choose k elements from a list, with
-- repetitions. "Symmetric power" for lists. See also
-- Math.Combinat.Compositions. TODO: better name?
combine :: Int -> [a] -> [[a]]
-- | A synonym for combine.
compose :: Int -> [a] -> [[a]]
-- | "Tensor power" for lists. Special case of listTensor:
--
--
-- tuplesFromList k xs == listTensor (replicate k xs)
--
--
-- See also Math.Combinat.Tuples. TODO: better name?
tuplesFromList :: Int -> [a] -> [[a]]
-- | "Tensor product" for lists.
listTensor :: [[a]] -> [[a]]
-- | Sublists of a list having given number of elements. Synonym for
-- choose.
kSublists :: Int -> [a] -> [[a]]
-- | All sublists of a list.
sublists :: [a] -> [[a]]
-- | # = binom { n } { k }.
countKSublists :: Int -> Int -> Integer
-- | # = 2^n.
countSublists :: Int -> Integer
-- | randomChoice k n returns a uniformly random choice of
-- k elements from the set [1..n]
--
-- Example:
--
--
-- do
-- cs <- replicateM 10000 (getStdRandom (randomChoice 3 7))
-- mapM_ print $ histogram cs
--
randomChoice :: RandomGen g => Int -> Int -> g -> ([Int], g)
-- | Compositions.
--
-- See eg.
-- http://en.wikipedia.org/wiki/Composition_%28combinatorics%29
module Math.Combinat.Compositions
-- | A composition of an integer n into k parts is
-- an ordered k-tuple of nonnegative (sometimes positive)
-- integers whose sum is n.
type Composition = [Int]
-- | Compositions fitting into a given shape and having a given degree. The
-- order is lexicographic, that is,
--
--
-- sort cs == cs where cs = compositions' shape k
--
compositions' :: [Int] -> Int -> [[Int]]
countCompositions' :: [Int] -> Int -> Integer
-- | All positive compositions of a given number (filtrated by the length).
-- Total number of these is 2^(n-1)
allCompositions1 :: Int -> [[Composition]]
-- | All compositions fitting into a given shape.
allCompositions' :: [Int] -> [[Composition]]
-- | Nonnegative compositions of a given length.
compositions :: Integral a => a -> a -> [[Int]]
-- | # = \binom { len+d-1 } { len-1 }
countCompositions :: Integral a => a -> a -> Integer
-- | Positive compositions of a given length.
compositions1 :: Integral a => a -> a -> [[Int]]
countCompositions1 :: Integral a => a -> a -> Integer
-- | randomComposition k n returns a uniformly random composition
-- of the number n as an (ordered) sum of k
-- nonnegative numbers
randomComposition :: RandomGen g => Int -> Int -> g -> ([Int], g)
-- | randomComposition1 k n returns a uniformly random composition
-- of the number n as an (ordered) sum of k
-- positive numbers
randomComposition1 :: RandomGen g => Int -> Int -> g -> ([Int], g)
-- | Permutations.
--
-- See eg.: Donald E. Knuth: The Art of Computer Programming, vol 4,
-- pre-fascicle 2B.
--
-- WARNING: As of version 0.2.8.0, I changed the convention of how
-- permutations are represented internally. Also now they act on the
-- right by default!
module Math.Combinat.Permutations
-- | A permutation. Internally it is an (unboxed) array of the integers
-- [1..n], with indexing range also being (1,n).
--
-- If this array of integers is [p1,p2,...,pn], then in two-line
-- notations, that represents the permutation
--
--
-- ( 1 2 3 ... n )
-- ( p1 p2 p3 ... pn )
--
--
-- That is, it is the permutation sigma whose (right) action on
-- the set [1..n] is
--
--
-- sigma(1) = p1
-- sigma(2) = p2
-- ...
--
--
-- (NOTE: this changed at version 0.2.8.0!)
newtype Permutation
Permutation :: (UArray Int Int) -> Permutation
fromPermutation :: Permutation -> [Int]
-- | Note: this is slower than permutationUArray
permutationArray :: Permutation -> Array Int Int
permutationUArray :: Permutation -> UArray Int Int
-- | Note: Indexing starts from 1.
uarrayToPermutationUnsafe :: UArray Int Int -> Permutation
-- | Checks whether the input is a permutation of the numbers
-- [1..n].
isPermutation :: [Int] -> Bool
-- | Checks whether the input is a permutation of the numbers
-- [1..n].
maybePermutation :: [Int] -> Maybe Permutation
-- | Checks the input.
toPermutation :: [Int] -> Permutation
-- | Assumes that the input is a permutation of the numbers
-- [1..n].
toPermutationUnsafe :: [Int] -> Permutation
-- | Returns n, where the input is a permutation of the numbers
-- [1..n]
permutationSize :: Permutation -> Int
-- | Disjoint cycle notation for permutations. Internally it is
-- [[Int]].
--
-- The cycles are to be understood as follows: a cycle
-- [c1,c2,...,ck] means the permutation
--
--
-- ( c1 c2 c3 ... ck )
-- ( c2 c3 c4 ... c1 )
--
newtype DisjointCycles
DisjointCycles :: [[Int]] -> DisjointCycles
fromDisjointCycles :: DisjointCycles -> [[Int]]
disjointCyclesUnsafe :: [[Int]] -> DisjointCycles
-- | Convert to disjoint cycle notation.
--
-- This is compatible with Maple's convert(perm,'disjcyc') and
-- also with Mathematica's PermutationCycles[perm]
--
-- Note however, that for example Mathematica uses the top row to
-- represent a permutation, while we use the bottom row - thus
-- even though this function looks identical, the meaning of both
-- the input and output is different!
permutationToDisjointCycles :: Permutation -> DisjointCycles
disjointCyclesToPermutation :: Int -> DisjointCycles -> Permutation
numberOfCycles :: HasNumberOfCycles p => p -> Int
-- | Checks whether the permutation is the identity permutation
isIdentityPermutation :: Permutation -> Bool
-- | Checks whether the permutation is the reverse permutation
-- @[n,n-1,n-2,...,2,1].
isReversePermutation :: Permutation -> Bool
isEvenPermutation :: Permutation -> Bool
isOddPermutation :: Permutation -> Bool
signOfPermutation :: Permutation -> Sign
-- | Plus 1 or minus 1.
signValueOfPermutation :: Num a => Permutation -> a
isCyclicPermutation :: Permutation -> Bool
-- | A transposition (swapping two elements).
--
-- transposition n (i,j) is the permutation of size n
-- which swaps i'th and j'th elements.
transposition :: Int -> (Int, Int) -> Permutation
-- | Product of transpositions.
--
--
-- transpositions n list == multiplyMany [ transposition n pair | pair <- list ]
--
transpositions :: Int -> [(Int, Int)] -> Permutation
-- | adjacentTransposition n k swaps the elements k and
-- (k+1).
adjacentTransposition :: Int -> Int -> Permutation
-- | Product of adjacent transpositions.
--
--
-- adjacentTranspositions n list == multiplyMany [ adjacentTransposition n idx | idx <- list ]
--
adjacentTranspositions :: Int -> [Int] -> Permutation
-- | The permutation which cycles a list left by one step:
--
--
-- permuteList (cycleLeft 5) "abcde" == "bcdea"
--
--
-- Or in two-line notation:
--
--
-- ( 1 2 3 4 5 )
-- ( 2 3 4 5 1 )
--
cycleLeft :: Int -> Permutation
-- | The permutation which cycles a list right by one step:
--
--
-- permuteList (cycleRight 5) "abcde" == "eabcd"
--
--
-- Or in two-line notation:
--
--
-- ( 1 2 3 4 5 )
-- ( 5 1 2 3 4 )
--
cycleRight :: Int -> Permutation
-- | The permutation [n,n-1,n-2,...,2,1]. Note that it is the
-- inverse of itself.
reversePermutation :: Int -> Permutation
-- | An inversion of a permutation sigma is a pair
-- (i,j) such that i<j and sigma(i) >
-- sigma(j).
--
-- This functions returns the inversion of a permutation.
inversions :: Permutation -> [(Int, Int)]
-- | Returns the number of inversions:
--
--
-- numberOfInversions perm = length (inversions perm)
--
--
-- Synonym for numberOfInversionsMerge
numberOfInversions :: Permutation -> Int
-- | Returns the number of inversions, using the definition, thus it's
-- O(n^2).
numberOfInversionsNaive :: Permutation -> Int
-- | Returns the number of inversions, using the merge-sort algorithm. This
-- should be O(n*log(n))
numberOfInversionsMerge :: Permutation -> Int
-- | Bubble sorts breaks a permutation into the product of adjacent
-- transpositions:
--
--
-- multiplyMany' n (map (transposition n) $ bubbleSort2 perm) == perm
--
--
-- Note that while this is not unique, the number of transpositions
-- equals the number of inversions.
bubbleSort2 :: Permutation -> [(Int, Int)]
-- | Another version of bubble sort. An entry i in the return
-- sequence means the transposition (i,i+1):
--
--
-- multiplyMany' n (map (adjacentTransposition n) $ bubbleSort perm) == perm
--
bubbleSort :: Permutation -> [Int]
-- | The identity (or trivial) permutation.
identity :: Int -> Permutation
-- | The inverse permutation.
inverse :: Permutation -> Permutation
-- | Multiplies two permutations together: p multiply q
-- means the permutation when we first apply p, and then
-- q (that is, the natural action is the right action)
--
-- See also permute for our conventions.
multiply :: Permutation -> Permutation -> Permutation
infixr 7 `multiply`
-- | Multiply together a non-empty list of permutations (the reason
-- for requiring the list to be non-empty is that we don't know the size
-- of the result). See also multiplyMany'.
multiplyMany :: [Permutation] -> Permutation
-- | Multiply together a (possibly empty) list of permutations, all of
-- which has size n
multiplyMany' :: Int -> [Permutation] -> Permutation
-- | Right action of a permutation on a set. If our permutation is
-- encoded with the sequence [p1,p2,...,pn], then in the
-- two-line notation we have
--
--
-- ( 1 2 3 ... n )
-- ( p1 p2 p3 ... pn )
--
--
-- We adopt the convention that permutations act on the right (as
-- in Knuth):
--
--
-- permute pi2 (permute pi1 set) == permute (pi1 `multiply` pi2) set
--
--
-- Synonym to permuteRight
permute :: IArray arr b => Permutation -> arr Int b -> arr Int b
-- | Right action on lists. Synonym to permuteListRight
permuteList :: Permutation -> [a] -> [a]
-- | The left (opposite) action of the permutation group.
--
--
-- permuteLeft pi2 (permuteLeft pi1 set) == permuteLeft (pi2 `multiply` pi1) set
--
--
-- It is related to permuteLeft via:
--
--
-- permuteLeft pi arr == permuteRight (inverse pi) arr
-- permuteRight pi arr == permuteLeft (inverse pi) arr
--
permuteLeft :: IArray arr b => Permutation -> arr Int b -> arr Int b
-- | The right (standard) action of permutations on sets.
--
--
-- permuteRight pi2 (permuteRight pi1 set) == permuteRight (pi1 `multiply` pi2) set
--
--
-- The second argument should be an array with bounds (1,n). The
-- function checks the array bounds.
permuteRight :: IArray arr b => Permutation -> arr Int b -> arr Int b
-- | The left (opposite) action on a list. The list should be of length
-- n.
--
--
-- permuteLeftList perm set == permuteList (inverse perm) set
-- fromPermutation (inverse perm) == permuteLeftList perm [1..n]
--
permuteLeftList :: forall a. Permutation -> [a] -> [a]
-- | The right (standard) action on a list. The list should be of length
-- n.
--
--
-- fromPermutation perm == permuteRightList perm [1..n]
--
permuteRightList :: forall a. Permutation -> [a] -> [a]
-- | Synonym for twoLineNotation
asciiPermutation :: Permutation -> ASCII
asciiDisjointCycles :: DisjointCycles -> ASCII
-- | The standard two-line notation, moving the element indexed by the top
-- row into the place indexed by the corresponding element in the bottom
-- row.
twoLineNotation :: Permutation -> ASCII
-- | The inverse two-line notation, where the it's the bottom line which is
-- in standard order. The columns of this are a permutation of the
-- columns twoLineNotation.
--
-- Remark: the top row of inverseTwoLineNotation perm is the
-- same as the bottom row of twoLineNotation (inverse perm).
inverseTwoLineNotation :: Permutation -> ASCII
-- | Two-line notation for any set of numbers
genericTwoLineNotation :: [(Int, Int)] -> ASCII
-- | A synonym for permutationsNaive
permutations :: Int -> [Permutation]
_permutations :: Int -> [[Int]]
-- | All permutations of [1..n] in lexicographic order, naive
-- algorithm.
permutationsNaive :: Int -> [Permutation]
_permutationsNaive :: Int -> [[Int]]
-- | # = n!
countPermutations :: Int -> Integer
-- | A synonym for randomPermutationDurstenfeld.
randomPermutation :: RandomGen g => Int -> g -> (Permutation, g)
_randomPermutation :: RandomGen g => Int -> g -> ([Int], g)
-- | A synonym for randomCyclicPermutationSattolo.
randomCyclicPermutation :: RandomGen g => Int -> g -> (Permutation, g)
_randomCyclicPermutation :: RandomGen g => Int -> g -> ([Int], g)
-- | Generates a uniformly random permutation of [1..n].
-- Durstenfeld's algorithm (see
-- http://en.wikipedia.org/wiki/Knuth_shuffle).
randomPermutationDurstenfeld :: RandomGen g => Int -> g -> (Permutation, g)
-- | Generates a uniformly random cyclic permutation of
-- [1..n]. Sattolo's algorithm (see
-- http://en.wikipedia.org/wiki/Knuth_shuffle).
randomCyclicPermutationSattolo :: RandomGen g => Int -> g -> (Permutation, g)
-- | Generates all permutations of a multiset. The order is lexicographic.
-- A synonym for fasc2B_algorithm_L
permuteMultiset :: (Eq a, Ord a) => [a] -> [[a]]
-- | # = \frac { (sum_i n_i) ! } { \prod_i (n_i !) }
countPermuteMultiset :: (Eq a, Ord a) => [a] -> Integer
-- | Generates all permutations of a multiset (based on "algorithm L" in
-- Knuth; somewhat less efficient). The order is lexicographic.
fasc2B_algorithm_L :: (Eq a, Ord a) => [a] -> [[a]]
instance GHC.Read.Read Math.Combinat.Permutations.DisjointCycles
instance GHC.Show.Show Math.Combinat.Permutations.DisjointCycles
instance GHC.Classes.Ord Math.Combinat.Permutations.DisjointCycles
instance GHC.Classes.Eq Math.Combinat.Permutations.DisjointCycles
instance GHC.Classes.Ord Math.Combinat.Permutations.Permutation
instance GHC.Classes.Eq Math.Combinat.Permutations.Permutation
instance GHC.Show.Show Math.Combinat.Permutations.Permutation
instance GHC.Read.Read Math.Combinat.Permutations.Permutation
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Permutations.Permutation
instance Math.Combinat.Classes.HasWidth Math.Combinat.Permutations.Permutation
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Permutations.DisjointCycles
instance Math.Combinat.Classes.HasNumberOfCycles Math.Combinat.Permutations.DisjointCycles
instance Math.Combinat.Classes.HasNumberOfCycles Math.Combinat.Permutations.Permutation
-- | Partitions of integers. Integer partitions are nonincreasing sequences
-- of positive integers.
--
-- See:
--
--
--
-- For example the partition
--
--
-- Partition [8,6,3,3,1]
--
--
-- can be represented by the (English notation) Ferrers diagram:
--
module Math.Combinat.Partitions.Integer
-- | A partition of an integer. The additional invariant enforced here is
-- that partitions are monotone decreasing sequences of positive
-- integers. The Ord instance is lexicographical.
newtype Partition
Partition :: [Int] -> Partition
-- | Sorts the input, and cuts the nonpositive elements.
mkPartition :: [Int] -> Partition
-- | Assumes that the input is decreasing.
toPartitionUnsafe :: [Int] -> Partition
-- | Checks whether the input is an integer partition. See the note at
-- isPartition!
toPartition :: [Int] -> Partition
-- | This returns True if the input is non-increasing sequence of
-- positive integers (possibly empty); False otherwise.
isPartition :: [Int] -> Bool
isEmptyPartition :: Partition -> Bool
emptyPartition :: Partition
fromPartition :: Partition -> [Int]
-- | The first element of the sequence.
partitionHeight :: Partition -> Int
-- | The length of the sequence (that is, the number of parts).
partitionWidth :: Partition -> Int
heightWidth :: Partition -> (Int, Int)
-- | The weight of the partition (that is, the sum of the corresponding
-- sequence).
partitionWeight :: Partition -> Int
-- | The dual (or conjugate) partition.
dualPartition :: Partition -> Partition
data Pair
Pair :: !Int -> !Int -> Pair
_dualPartition :: [Int] -> [Int]
-- | A simpler, but bit slower (about twice?) implementation of dual
-- partition
_dualPartitionNaive :: [Int] -> [Int]
-- | From a sequence [a1,a2,..,an] computes the sequence of
-- differences [a1-a2,a2-a3,...,an-0]
diffSequence :: [Int] -> [Int]
-- | Example:
--
--
-- elements (toPartition [5,4,1]) ==
-- [ (1,1), (1,2), (1,3), (1,4), (1,5)
-- , (2,1), (2,2), (2,3), (2,4)
-- , (3,1)
-- ]
--
elements :: Partition -> [(Int, Int)]
_elements :: [Int] -> [(Int, Int)]
-- | We convert a partition to exponential form. (i,e) mean
-- (i^e); for example [(1,4),(2,3)] corresponds to
-- (1^4)(2^3) = [2,2,2,1,1,1,1]. Another example:
--
--
-- toExponentialForm (Partition [5,5,3,2,2,2,2,1,1]) == [(1,2),(2,4),(3,1),(5,2)]
--
toExponentialForm :: Partition -> [(Int, Int)]
_toExponentialForm :: [Int] -> [(Int, Int)]
fromExponentialFrom :: [(Int, Int)] -> Partition
-- | Computes the number of "automorphisms" of a given integer partition.
countAutomorphisms :: Partition -> Integer
_countAutomorphisms :: [Int] -> Integer
-- | Partitions of d.
partitions :: Int -> [Partition]
-- | Partitions of d, as lists
_partitions :: Int -> [[Int]]
-- | Number of partitions of n
countPartitions :: Int -> Integer
-- | This uses countPartitions', and thus is slow
countPartitionsNaive :: Int -> Integer
-- | Infinite list of number of partitions of 0,1,2,...
--
-- This uses the infinite product formula the generating function of
-- partitions, recursively expanding it; it is quite fast.
--
--
-- partitionCountList == map countPartitions [0..]
--
partitionCountList :: [Integer]
-- | Naive infinite list of number of partitions of 0,1,2,...
--
--
-- partitionCountListNaive == map countPartitionsNaive [0..]
--
--
-- This is much slower than the power series expansion above.
partitionCountListNaive :: [Integer]
-- | All integer partitions up to a given degree (that is, all integer
-- partitions whose sum is less or equal to d)
allPartitions :: Int -> [Partition]
-- | All integer partitions up to a given degree (that is, all integer
-- partitions whose sum is less or equal to d), grouped by
-- weight
allPartitionsGrouped :: Int -> [[Partition]]
-- | All integer partitions fitting into a given rectangle.
allPartitions' :: (Int, Int) -> [Partition]
-- | All integer partitions fitting into a given rectangle, grouped by
-- weight.
allPartitionsGrouped' :: (Int, Int) -> [[Partition]]
-- | # = \binom { h+w } { h }
countAllPartitions' :: (Int, Int) -> Integer
countAllPartitions :: Int -> Integer
-- | Integer partitions of d, fitting into a given rectangle, as
-- lists.
_partitions' :: (Int, Int) -> Int -> [[Int]]
-- | Partitions of d, fitting into a given rectangle. The order is again
-- lexicographic.
partitions' :: (Int, Int) -> Int -> [Partition]
countPartitions' :: (Int, Int) -> Int -> Integer
-- | Uniformly random partition of the given weight.
--
-- NOTE: This algorithm is effective for small n-s (say
-- n up to a few hundred / one thousand it should work nicely),
-- and the first time it is executed may be slower (as it needs to build
-- the table partitionCountList first)
--
-- Algorithm of Nijenhuis and Wilf (1975); see
--
--
-- - Knuth Vol 4A, pre-fascicle 3B, exercise 47;
-- - Nijenhuis and Wilf: Combinatorial Algorithms for Computers and
-- Calculators, chapter 10
--
randomPartition :: RandomGen g => Int -> g -> (Partition, g)
-- | Generates several uniformly random partitions of n at the
-- same time. Should be a little bit faster then generating them
-- individually.
randomPartitions :: forall g. RandomGen g => Int -> Int -> g -> ([Partition], g)
-- | q `dominates` p returns True if q >= p
-- in the dominance order of partitions (this is partial ordering on the
-- set of partitions of n).
--
-- See http://en.wikipedia.org/wiki/Dominance_order
dominates :: Partition -> Partition -> Bool
-- | Lists all partitions of the same weight as lambda and also
-- dominated by lambda (that is, all partial sums are less or
-- equal):
--
--
-- dominatedPartitions lam == [ mu | mu <- partitions (weight lam), lam `dominates` mu ]
--
dominatedPartitions :: Partition -> [Partition]
_dominatedPartitions :: [Int] -> [[Int]]
-- | Lists all partitions of the sime weight as mu and also
-- dominating mu (that is, all partial sums are greater or
-- equal):
--
--
-- dominatingPartitions mu == [ lam | lam <- partitions (weight mu), lam `dominates` mu ]
--
dominatingPartitions :: Partition -> [Partition]
_dominatingPartitions :: [Int] -> [[Int]]
-- | Lists partitions of n into k parts.
--
--
-- sort (partitionsWithKParts k n) == sort [ p | p <- partitions n , numberOfParts p == k ]
--
--
-- Naive recursive algorithm.
partitionsWithKParts :: Int -> Int -> [Partition]
countPartitionsWithKParts :: Int -> Int -> Integer
-- | Partitions of n with only odd parts
partitionsWithOddParts :: Int -> [Partition]
-- | Partitions of n with distinct parts.
--
-- Note:
--
--
-- length (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)
--
partitionsWithDistinctParts :: Int -> [Partition]
-- | Returns True of the first partition is a subpartition (that
-- is, fit inside) of the second. This includes equality
isSubPartitionOf :: Partition -> Partition -> Bool
-- | This is provided for convenience/completeness only, as:
--
--
-- isSuperPartitionOf q p == isSubPartitionOf p q
--
isSuperPartitionOf :: Partition -> Partition -> Bool
-- | Sub-partitions of a given partition with the given weight:
--
--
-- sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]
--
subPartitions :: Int -> Partition -> [Partition]
_subPartitions :: Int -> [Int] -> [[Int]]
-- | All sub-partitions of a given partition
allSubPartitions :: Partition -> [Partition]
_allSubPartitions :: [Int] -> [[Int]]
-- | Super-partitions of a given partition with the given weight:
--
--
-- sort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]
--
superPartitions :: Int -> Partition -> [Partition]
_superPartitions :: Int -> [Int] -> [[Int]]
-- | The Pieri rule computes s[lambda]*h[n] as a sum of
-- s[mu]-s (each with coefficient 1).
--
-- See for example http://en.wikipedia.org/wiki/Pieri's_formula
pieriRule :: Partition -> Int -> [Partition]
-- | The dual Pieri rule computes s[lambda]*e[n] as a sum of
-- s[mu]-s (each with coefficient 1)
dualPieriRule :: Partition -> Int -> [Partition]
-- | Which orientation to draw the Ferrers diagrams. For example, the
-- partition [5,4,1] corrsponds to:
--
-- In standard English notation:
--
--
-- @@@@@
-- @@@@
-- @
--
--
-- In English notation rotated by 90 degrees counter-clockwise:
--
--
-- @
-- @@
-- @@
-- @@
-- @@@
--
--
-- And in French notation:
--
--
-- @
-- @@@@
-- @@@@@
--
data PartitionConvention
-- | English notation
EnglishNotation :: PartitionConvention
-- | English notation rotated by 90 degrees counterclockwise
EnglishNotationCCW :: PartitionConvention
-- | French notation (mirror of English notation to the x axis)
FrenchNotation :: PartitionConvention
-- | Synonym for asciiFerrersDiagram' EnglishNotation '@'
--
-- Try for example:
--
--
-- autoTabulate RowMajor (Right 8) (map asciiFerrersDiagram $ partitions 9)
--
asciiFerrersDiagram :: Partition -> ASCII
asciiFerrersDiagram' :: PartitionConvention -> Char -> Partition -> ASCII
instance GHC.Show.Show Math.Combinat.Partitions.Integer.PartitionConvention
instance GHC.Classes.Eq Math.Combinat.Partitions.Integer.PartitionConvention
instance GHC.Read.Read Math.Combinat.Partitions.Integer.Partition
instance GHC.Show.Show Math.Combinat.Partitions.Integer.Partition
instance GHC.Classes.Ord Math.Combinat.Partitions.Integer.Partition
instance GHC.Classes.Eq Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasNumberOfParts Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.CanBeEmpty Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasHeight Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasWidth Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasWeight Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasDuality Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Partitions.Integer.Partition
-- | Partitions of integers and multisets. Integer partitions are
-- nonincreasing sequences of positive integers.
--
-- See:
--
--
module Math.Combinat.Partitions
-- | Young tableaux and similar gadgets.
--
-- See e.g. William Fulton: Young Tableaux, with Applications to
-- Representation theory and Geometry (CUP 1997).
--
-- The convention is that we use the English notation, and we store the
-- tableaux as lists of the rows.
--
-- That is, the following standard Young tableau of shape [5,4,1]
--
--
-- 1 3 4 6 7
-- 2 5 8 10
-- 9
--
--
--
-- is encoded conveniently as
--
--
-- [ [ 1 , 3 , 4 , 6 , 7 ]
-- , [ 2 , 5 , 8 ,10 ]
-- , [ 9 ]
-- ]
--
module Math.Combinat.Tableaux
-- | A tableau is simply represented as a list of lists.
type Tableau a = [[a]]
-- | ASCII diagram of a tableau
asciiTableau :: Show a => Tableau a -> ASCII
_tableauShape :: Tableau a -> [Int]
-- | The shape of a tableau
tableauShape :: Tableau a -> Partition
-- | Number of entries
tableauWeight :: Tableau a -> Int
-- | The dual of the tableau is the mirror image to the main diagonal.
dualTableau :: Tableau a -> Tableau a
-- | The content of a tableau is the list of its entries. The ordering is
-- from the left to the right and then from the top to the bottom
tableauContent :: Tableau a -> [a]
-- | An element (i,j) of the resulting tableau (which has shape of
-- the given partition) means that the vertical part of the hook has
-- length i, and the horizontal part j. The hook
-- length is thus i+j-1.
--
-- Example:
--
--
-- > mapM_ print $ hooks $ toPartition [5,4,1]
-- [(3,5),(2,4),(2,3),(2,2),(1,1)]
-- [(2,4),(1,3),(1,2),(1,1)]
-- [(1,1)]
--
hooks :: Partition -> Tableau (Int, Int)
hookLengths :: Partition -> Tableau Int
-- | The row word of a tableau is the list of its entry read from
-- the right to the left and then from the top to the bottom.
rowWord :: Tableau a -> [a]
-- | Semistandard tableaux can be reconstructed from their row words
rowWordToTableau :: Ord a => [a] -> Tableau a
-- | The column word of a tableau is the list of its entry read from
-- the bottom to the top and then from the left to the right
columnWord :: Tableau a -> [a]
-- | Standard tableaux can be reconstructed from either their column
-- or row words
columnWordToTableau :: Ord a => [a] -> Tableau a
-- | Checks whether a sequence of positive integers is a lattice
-- word, which means that in every initial part of the sequence any
-- number i occurs at least as often as the number i+1
isLatticeWord :: [Int] -> Bool
-- | A tableau is semistandard if its entries are weekly increasing
-- horizontally and strictly increasing vertically
isSemiStandardTableau :: Tableau Int -> Bool
-- | Semistandard Young tableaux of given shape, "naive" algorithm
semiStandardYoungTableaux :: Int -> Partition -> [Tableau Int]
-- | Stanley's hook formula (cf. Fulton page 55)
countSemiStandardYoungTableaux :: Int -> Partition -> Integer
-- | A tableau is standard if it is semistandard and its content is
-- exactly [1..n], where n is the weight.
isStandardTableau :: Tableau Int -> Bool
-- | Standard Young tableaux of a given shape. Adapted from John
-- Stembridge,
-- http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux.
standardYoungTableaux :: Partition -> [Tableau Int]
-- | hook-length formula
countStandardYoungTableaux :: Partition -> Integer
instance Math.Combinat.Classes.CanBeEmpty (Math.Combinat.Tableaux.Tableau a)
instance GHC.Show.Show a => Math.Combinat.ASCII.DrawASCII (Math.Combinat.Tableaux.Tableau a)
instance Math.Combinat.Classes.HasShape (Math.Combinat.Tableaux.Tableau a) Math.Combinat.Partitions.Integer.Partition
instance Math.Combinat.Classes.HasWeight (Math.Combinat.Tableaux.Tableau a)
instance Math.Combinat.Classes.HasDuality (Math.Combinat.Tableaux.Tableau a)
-- | This module contains a function to generate (equivalence classes of)
-- triangular tableaux of size k, strictly increasing to the right
-- and to the bottom. For example
--
--
-- 1
-- 2 4
-- 3 5 8
-- 6 7 9 10
--
--
-- is such a tableau of size 4. The numbers filling a tableau always
-- consist of an interval [1..c]; c is called the
-- content of the tableaux. There is a unique tableau of minimal
-- content 2k-1:
--
--
-- 1
-- 2 3
-- 3 4 5
-- 4 5 6 7
--
--
-- Let us call the tableaux with maximal content (that is, m =
-- binomial (k+1) 2) standard. The number of such standard
-- tableaux are
--
--
-- 1, 1, 2, 12, 286, 33592, 23178480, ...
--
--
-- OEIS:A003121, "Strict sense ballot numbers",
-- https://oeis.org/A003121.
--
-- See R. M. Thrall, A combinatorial problem, Michigan Math. J. 1,
-- (1952), 81-88.
--
-- The number of tableaux with content c=m-d are
--
--
-- d= | 0 1 2 3 ...
-- -----+----------------------------------------------
-- k=2 | 1
-- k=3 | 2 1
-- k=4 | 12 18 8 1
-- k=5 | 286 858 1001 572 165 22 1
-- k=6 | 33592 167960 361114 436696 326196 155584 47320 8892 962 52 1
--
--
-- We call these "GT simplex tableaux" (in the lack of a better name),
-- since they are in bijection with the simplicial cones in a canonical
-- simplicial decompositions of the Gelfand-Tsetlin cones (the content
-- corresponds to the dimension), which encode the combinatorics of
-- Kostka numbers.
module Math.Combinat.Tableaux.GelfandTsetlin.Cone
-- | A tableau is simply represented as a list of lists.
type Tableau a = [[a]]
-- | Set of (i,j) pairs with i>=j>=1.
newtype Tri
Tri :: (Int, Int) -> Tri
[unTri] :: Tri -> (Int, Int)
-- | Triangular arrays
type TriangularArray a = Array Tri a
fromTriangularArray :: TriangularArray a -> Tableau a
triangularArrayUnsafe :: Tableau a -> TriangularArray a
asciiTriangularArray :: Show a => TriangularArray a -> ASCII
asciiTableau :: Show a => Tableau a -> ASCII
gtSimplexContent :: TriangularArray Int -> Int
_gtSimplexContent :: Tableau Int -> Int
-- | We can flip the numbers in the tableau so that the interval
-- [1..c] becomes [c..1]. This way we a get a maybe
-- more familiar form, when each row and each column is strictly
-- decreasing (to the right and to the bottom).
invertGTSimplexTableau :: TriangularArray Int -> TriangularArray Int
_invertGTSimplexTableau :: [[Int]] -> [[Int]]
-- | Generates all tableaux of size k. Effective for
-- k<=6.
gtSimplexTableaux :: Int -> [TriangularArray Int]
_gtSimplexTableaux :: Int -> [Tableau Int]
-- | Note: This is slow (it actually generates all the tableaux)
countGTSimplexTableaux :: Int -> [Int]
instance GHC.Show.Show Math.Combinat.Tableaux.GelfandTsetlin.Cone.Hole
instance GHC.Classes.Ord Math.Combinat.Tableaux.GelfandTsetlin.Cone.Hole
instance GHC.Classes.Eq Math.Combinat.Tableaux.GelfandTsetlin.Cone.Hole
instance GHC.Show.Show Math.Combinat.Tableaux.GelfandTsetlin.Cone.Tri
instance GHC.Classes.Ord Math.Combinat.Tableaux.GelfandTsetlin.Cone.Tri
instance GHC.Classes.Eq Math.Combinat.Tableaux.GelfandTsetlin.Cone.Tri
instance GHC.Arr.Ix Math.Combinat.Tableaux.GelfandTsetlin.Cone.Tri
instance GHC.Show.Show a => Math.Combinat.ASCII.DrawASCII (Math.Combinat.Tableaux.GelfandTsetlin.Cone.TriangularArray a)
-- | Plane partitions. See eg.
-- http://en.wikipedia.org/wiki/Plane_partition
--
-- Plane partitions are encoded as lists of lists of Z heights. For
-- example the plane partition in the picture
--
--
-- is encoded as
--
--
-- PlanePart [ [5,4,3,3,1]
-- , [4,4,2,1]
-- , [3,2]
-- , [2,1]
-- , [1]
-- , [1]
-- ]
--
module Math.Combinat.Partitions.Plane
-- | A plane partition encoded as a tablaeu (the "Z" heights are the
-- numbers)
newtype PlanePart
PlanePart :: [[Int]] -> PlanePart
fromPlanePart :: PlanePart -> [[Int]]
isValidPlanePart :: [[Int]] -> Bool
-- | Throws an exception if the input is not a plane partition
toPlanePart :: [[Int]] -> PlanePart
-- | The XY projected shape of a plane partition, as an integer partition
planePartShape :: PlanePart -> Partition
-- | The Z height of a plane partition
planePartZHeight :: PlanePart -> Int
planePartWeight :: PlanePart -> Int
singleLayer :: Partition -> PlanePart
-- | Stacks layers of partitions into a plane partition. Throws an
-- exception if they do not form a plane partition.
stackLayers :: [Partition] -> PlanePart
-- | Stacks layers of partitions into a plane partition. This is unsafe in
-- the sense that we don't check that the partitions fit on the top of
-- each other.
unsafeStackLayers :: [Partition] -> PlanePart
-- | The "layers" of a plane partition (in direction Z). We should
-- have
--
--
-- unsafeStackLayers (planePartLayers pp) == pp
--
planePartLayers :: PlanePart -> [Partition]
-- | Plane partitions of a given weight
planePartitions :: Int -> [PlanePart]
instance GHC.Show.Show Math.Combinat.Partitions.Plane.PlanePart
instance GHC.Classes.Ord Math.Combinat.Partitions.Plane.PlanePart
instance GHC.Classes.Eq Math.Combinat.Partitions.Plane.PlanePart
instance Math.Combinat.Classes.CanBeEmpty Math.Combinat.Partitions.Plane.PlanePart
instance Math.Combinat.Classes.HasWeight Math.Combinat.Partitions.Plane.PlanePart
-- | Some basic univariate power series expansions. This module is not
-- re-exported by Math.Combinat.
--
-- Note: the "convolveWithXXX" functions are much faster than
-- the equivalent (XXX `convolve`)!
--
-- TODO: better names for these functions.
module Math.Combinat.Numbers.Series
-- | The series [1,0,0,0,0,...], which is the neutral element for the
-- convolution.
unitSeries :: Num a => [a]
-- | Constant zero series
zeroSeries :: Num a => [a]
-- | Power series representing a constant function
constSeries :: Num a => a -> [a]
-- | The power series representation of the identity function x
idSeries :: Num a => [a]
-- | The power series representation of x^n
powerTerm :: Num a => Int -> [a]
addSeries :: Num a => [a] -> [a] -> [a]
sumSeries :: Num a => [[a]] -> [a]
subSeries :: Num a => [a] -> [a] -> [a]
negateSeries :: Num a => [a] -> [a]
scaleSeries :: Num a => a -> [a] -> [a]
mulSeries :: Num a => [a] -> [a] -> [a]
productOfSeries :: Num a => [[a]] -> [a]
-- | Convolution of series (that is, multiplication of power series). The
-- result is always an infinite list. Warning: This is slow!
convolve :: Num a => [a] -> [a] -> [a]
-- | Convolution (= product) of many series. Still slow!
convolveMany :: Num a => [[a]] -> [a]
-- | Given a power series, we iteratively compute its multiplicative
-- inverse
reciprocalSeries :: (Eq a, Fractional a) => [a] -> [a]
-- | Given a power series starting with 1, we can compute its
-- multiplicative inverse without divisions.
integralReciprocalSeries :: (Eq a, Num a) => [a] -> [a]
-- | g `composeSeries` f is the power series expansion of
-- g(f(x)). This is a synonym for flip substitute.
--
-- We require that the constant term of f is zero.
composeSeries :: (Eq a, Num a) => [a] -> [a] -> [a]
-- | substitute f g is the power series corresponding to
-- g(f(x)). Equivalently, this is the composition of univariate
-- functions (in the "wrong" order).
--
-- Note: for this to be meaningful in general (not depending on
-- convergence properties), we need that the constant term of f
-- is zero.
substitute :: (Eq a, Num a) => [a] -> [a] -> [a]
-- | Coefficients of the Lagrange inversion
lagrangeCoeff :: Partition -> Integer
-- | We expect the input series to match (0:1:_). The following is
-- true for the result (at least with exact arithmetic):
--
--
-- substitute f (integralLagrangeInversion f) == (0 : 1 : repeat 0)
-- substitute (integralLagrangeInversion f) f == (0 : 1 : repeat 0)
--
integralLagrangeInversion :: (Eq a, Num a) => [a] -> [a]
-- | We expect the input series to match (0:a1:_). with a1 nonzero
-- The following is true for the result (at least with exact arithmetic):
--
--
-- substitute f (lagrangeInversion f) == (0 : 1 : repeat 0)
-- substitute (lagrangeInversion f) f == (0 : 1 : repeat 0)
--
lagrangeInversion :: (Eq a, Fractional a) => [a] -> [a]
-- | Power series expansion of exp(x)
expSeries :: Fractional a => [a]
-- | Power series expansion of cos(x)
cosSeries :: Fractional a => [a]
-- | Power series expansion of sin(x)
sinSeries :: Fractional a => [a]
-- | Power series expansion of cosh(x)
coshSeries :: Fractional a => [a]
-- | Power series expansion of sinh(x)
sinhSeries :: Fractional a => [a]
-- | Power series expansion of log(1+x)
log1Series :: Fractional a => [a]
-- | Power series expansion of (1-Sqrt[1-4x])/(2x) (the
-- coefficients are the Catalan numbers)
dyckSeries :: Num a => [a]
-- | Power series expansion of
--
--
-- 1 / ( (1-x^k_1) * (1-x^k_2) * ... * (1-x^k_n) )
--
--
-- Example:
--
-- (coinSeries [2,3,5])!!k is the number of ways to pay
-- k dollars with coins of two, three and five dollars.
--
-- TODO: better name?
coinSeries :: [Int] -> [Integer]
-- | Generalization of the above to include coefficients: expansion of
--
--
-- 1 / ( (1-a_1*x^k_1) * (1-a_2*x^k_2) * ... * (1-a_n*x^k_n) )
--
coinSeries' :: Num a => [(a, Int)] -> [a]
convolveWithCoinSeries :: [Int] -> [Integer] -> [Integer]
convolveWithCoinSeries' :: Num a => [(a, Int)] -> [a] -> [a]
-- | Convolution of many pseries, that is, the expansion of the
-- reciprocal of a product of polynomials
productPSeries :: [[Int]] -> [Integer]
-- | The same, with coefficients.
productPSeries' :: Num a => [[(a, Int)]] -> [a]
convolveWithProductPSeries :: [[Int]] -> [Integer] -> [Integer]
-- | This is the most general function in this module; all the others are
-- special cases of this one.
convolveWithProductPSeries' :: Num a => [[(a, Int)]] -> [a] -> [a]
-- | The power series expansion of
--
--
-- 1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)
--
pseries :: [Int] -> [Integer]
-- | Convolve with (the expansion of)
--
--
-- 1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)
--
convolveWithPSeries :: [Int] -> [Integer] -> [Integer]
-- | The expansion of
--
--
-- 1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n)
--
pseries' :: Num a => [(a, Int)] -> [a]
-- | Convolve with (the expansion of)
--
--
-- 1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n)
--
convolveWithPSeries' :: Num a => [(a, Int)] -> [a] -> [a]
signedPSeries :: [(Sign, Int)] -> [Integer]
-- | Convolve with (the expansion of)
--
--
-- 1 / (1 +- x^k_1 +- x^k_2 +- x^k_3 +- ... +- x^k_n)
--
--
-- Should be faster than using convolveWithPSeries'. Note:
-- Plus corresponds to the coefficient -1 in
-- pseries' (since there is a minus sign in the definition there)!
convolveWithSignedPSeries :: [(Sign, Int)] -> [Integer] -> [Integer]
-- | Braids. See eg. https://en.wikipedia.org/wiki/Braid_group
--
-- Based on:
--
--
--
-- Note: This module GHC 7.8, since we use type-level naturals to
-- parametrize the Braid type.
module Math.Combinat.Groups.Braid
-- | A standard Artin generator of a braid: Sigma i represents
-- twisting the neighbour strands i and (i+1), such
-- that strand i goes under strand (i+1).
--
-- Note: The strands are numbered 1..n.
data BrGen
-- | i goes under (i+1)
Sigma :: !Int -> BrGen
-- | i goes above (i+1)
SigmaInv :: !Int -> BrGen
-- | The strand (more precisely, the first of the two strands) the
-- generator twistes
brGenIdx :: BrGen -> Int
brGenSign :: BrGen -> Sign
brGenSignIdx :: BrGen -> (Sign, Int)
-- | The inverse of a braid generator
invBrGen :: BrGen -> BrGen
-- | The braid group B_n on n strands. The number
-- n is encoded as a type level natural in the type parameter.
--
-- Braids are represented as words in the standard generators and their
-- inverses.
newtype Braid (n :: Nat)
Braid :: [BrGen] -> Braid
-- | The number of strands in the braid
numberOfStrands :: KnownNat n => Braid n -> Int
-- | Sometimes we want to hide the type-level parameter n, for
-- example when dynamically creating braids whose size is known only at
-- runtime.
data SomeBraid
SomeBraid :: (Braid n) -> SomeBraid
someBraid :: Int -> (forall (n :: Nat). KnownNat n => Braid n) -> SomeBraid
withSomeBraid :: SomeBraid -> (forall n. KnownNat n => Braid n -> a) -> a
mkBraid :: (forall n. KnownNat n => Braid n -> a) -> Int -> [BrGen] -> a
withBraid :: Int -> (forall (n :: Nat). KnownNat n => Braid n) -> (forall (n :: Nat). KnownNat n => Braid n -> a) -> a
braidWord :: Braid n -> [BrGen]
braidWordLength :: Braid n -> Int
-- | Embeds a smaller braid group into a bigger braid group
extend :: (n1 <= n2) => Braid n1 -> Braid n2
-- | Apply "free reduction" to the word, that is, iteratively remove
-- sigma_i sigma_i^-1 pairs. The resulting braid is clearly
-- equivalent to the original.
freeReduceBraidWord :: Braid n -> Braid n
-- | The braid generator sigma_i as a braid
sigma :: KnownNat n => Int -> Braid (n :: Nat)
-- | The braid generator sigma_i^(-1) as a braid
sigmaInv :: KnownNat n => Int -> Braid (n :: Nat)
-- | doubleSigma s t (for s<t)is the generator
-- sigma_{s,t} in Birman-Ko-Lee's "new presentation". It twistes
-- the strands s and t while going over all other
-- strands. For t==s+1 we get back sigma s
doubleSigma :: KnownNat n => Int -> Int -> Braid (n :: Nat)
-- | positiveWord [2,5,1] is shorthand for the word
-- sigma_2*sigma_5*sigma_1.
positiveWord :: KnownNat n => [Int] -> Braid (n :: Nat)
-- | The (positive) half-twist of all the braid strands, usually denoted by
-- Delta.
halfTwist :: KnownNat n => Braid n
-- | The untyped version of halfTwist
_halfTwist :: Int -> [Int]
-- | Synonym for halfTwist
theGarsideBraid :: KnownNat n => Braid n
-- | The inner automorphism defined by tau(X) = Delta^-1 X Delta,
-- where Delta is the positive half-twist.
--
-- This sends each generator sigma_j to sigma_(n-j).
tau :: KnownNat n => Braid n -> Braid n
-- | The involution tau on permutations (permutation braids)
tauPerm :: Permutation -> Permutation
-- | The trivial braid
identity :: Braid n
-- | The inverse of a braid. Note: we do not perform reduction here, as a
-- word is reduced if and only if its inverse is reduced.
inverse :: Braid n -> Braid n
-- | Composes two braids, doing free reduction on the result (that is,
-- removing (sigma_k * sigma_k^-1) pairs@)
compose :: Braid n -> Braid n -> Braid n
composeMany :: [Braid n] -> Braid n
-- | Composes two braids without doing any reduction.
composeDontReduce :: Braid n -> Braid n -> Braid n
-- | A braid is pure if its permutation is trivial
isPureBraid :: KnownNat n => Braid n -> Bool
-- | Returns the left-to-right permutation associated to the braid. We
-- follow the strands from the left to the right (or from the top
-- to the bottom), and return the permutation taking the left side to the
-- right side.
--
-- This is compatible with right (standard) action of the
-- permutations: permuteRight (braidPermutationRight b1)
-- corresponds to the left-to-right permutation of the strands; also:
--
--
-- (braidPermutation b1) `multiply` (braidPermutation b2) == braidPermutation (b1 `compose` b2)
--
--
-- Writing the right numbering of the strands below the left numbering,
-- we got the two-line notation of the permutation.
braidPermutation :: KnownNat n => Braid n -> Permutation
-- | This is an untyped version of braidPermutation
_braidPermutation :: Int -> [Int] -> Permutation
-- | A positive braid word contains only positive (Sigma)
-- generators.
isPositiveBraidWord :: KnownNat n => Braid n -> Bool
-- | A permutation braid is a positive braid where any two strands
-- cross at most one, and positively.
isPermutationBraid :: KnownNat n => Braid n -> Bool
-- | Untyped version of isPermutationBraid for positive words.
_isPermutationBraid :: Int -> [Int] -> Bool
-- | For any permutation this functions returns a permutation braid
-- realizing that permutation. Note that this is not unique, so we make
-- an arbitrary choice (except for the permutation [n,n-1..1]
-- reversing the order, in which case the result must be the half-twist
-- braid).
--
-- The resulting braid word will have a length at most choose n
-- 2 (and will have that length only for the permutation
-- [n,n-1..1])
--
--
-- braidPermutationRight (permutationBraid perm) == perm
-- isPermutationBraid (permutationBraid perm) == True
--
permutationBraid :: KnownNat n => Permutation -> Braid n
-- | Untyped version of permutationBraid
_permutationBraid :: Permutation -> [Int]
-- | Returns the individual "phases" of the a permutation braid realizing
-- the given permutation.
_permutationBraid' :: Permutation -> [[Int]]
-- | We compute the linking numbers between all pairs of strands:
--
--
-- linkingMatrix braid ! (i,j) == strandLinking braid i j
--
linkingMatrix :: KnownNat n => Braid n -> UArray (Int, Int) Int
-- | Untyped version of linkingMatrix
_linkingMatrix :: Int -> [BrGen] -> UArray (Int, Int) Int
-- | The linking number between two strands numbered i and
-- j (numbered such on the left side).
strandLinking :: KnownNat n => Braid n -> Int -> Int -> Int
-- | Bronfman's recursive formula for the reciprocial of the growth
-- function of positive braids. It was already known (by Deligne)
-- that these generating functions are reciprocials of polynomials;
-- Bronfman [1] gave a recursive formula for them.
--
--
-- let count n l = length $ nub $ [ braidNormalForm w | w <- allPositiveBraidWords n l ]
-- let convertPoly (1:cs) = zip (map negate cs) [1..]
-- pseries' (convertPoly $ bronfmanH n) == expandBronfmanH n == [ count n l | l <- [0..] ]
--
--
--
-- - [1] Aaron Bronfman: Growth functions of a class of monoids.
-- Preprint, 2001
--
bronfmanH :: Int -> [Int]
-- | An infinite list containing the Bronfman polynomials:
--
--
-- bronfmanH n = bronfmanHsList !! n
--
bronfmanHsList :: [[Int]]
-- | Expands the reciprocial of H(n) into an infinite power
-- series, giving the growth function of the positive braids on
-- n strands.
expandBronfmanH :: Int -> [Int]
-- | Horizontal braid diagram, drawn from left to right, with strands
-- numbered from the bottom to the top
horizBraidASCII :: KnownNat n => Braid n -> ASCII
-- | Horizontal braid diagram, drawn from left to right. The boolean flag
-- indicates whether to flip the strands vertically (True means
-- bottom-to-top, False means top-to-bottom)
horizBraidASCII' :: KnownNat n => Bool -> Braid n -> ASCII
-- | All positive braid words of the given length
allPositiveBraidWords :: KnownNat n => Int -> [Braid n]
-- | All braid words of the given length
allBraidWords :: KnownNat n => Int -> [Braid n]
-- | Untyped version of allPositiveBraidWords
_allPositiveBraidWords :: Int -> Int -> [[BrGen]]
-- | Untyped version of allBraidWords
_allBraidWords :: Int -> Int -> [[BrGen]]
-- | Random braid word of the given length
randomBraidWord :: (RandomGen g, KnownNat n) => Int -> g -> (Braid n, g)
-- | Random positive braid word of the given length
randomPositiveBraidWord :: (RandomGen g, KnownNat n) => Int -> g -> (Braid n, g)
-- | Given a braid word, we perturb it randomly m times using the
-- braid relations, so that the resulting new braid word is equivalent to
-- the original.
--
-- Useful for testing.
randomPerturbBraidWord :: forall n g. (RandomGen g, KnownNat n) => Int -> Braid n -> g -> (Braid n, g)
-- | This version of randomBraidWord may be convenient to avoid the
-- type level stuff
withRandomBraidWord :: RandomGen g => (forall n. KnownNat n => Braid n -> a) -> Int -> Int -> g -> (a, g)
-- | This version of randomPositiveBraidWord may be convenient to
-- avoid the type level stuff
withRandomPositiveBraidWord :: RandomGen g => (forall n. KnownNat n => Braid n -> a) -> Int -> Int -> g -> (a, g)
-- | Untyped version of randomBraidWord
_randomBraidWord :: (RandomGen g) => Int -> Int -> g -> ([BrGen], g)
-- | Untyped version of randomPositiveBraidWord
_randomPositiveBraidWord :: (RandomGen g) => Int -> Int -> g -> ([BrGen], g)
instance GHC.Show.Show (Math.Combinat.Groups.Braid.Braid n)
instance GHC.Show.Show Math.Combinat.Groups.Braid.BrGen
instance GHC.Classes.Ord Math.Combinat.Groups.Braid.BrGen
instance GHC.Classes.Eq Math.Combinat.Groups.Braid.BrGen
instance GHC.TypeLits.KnownNat n => Math.Combinat.ASCII.DrawASCII (Math.Combinat.Groups.Braid.Braid n)
-- | Normal form of braids, take 1.
--
-- We implement the Adyan-Thurston-ElRifai-Morton solution to the word
-- problem in braid groups.
--
-- Based on:
--
--
module Math.Combinat.Groups.Braid.NF
-- | A unique normal form for braids, called the left-greedy normal
-- form. It looks like Delta^i*P, where Delta is
-- the positive half-twist, i is an integer, and P is a
-- positive word, which can be further decomposed into non-Delta
-- permutation words; these words themselves are not unique, but
-- the permutations they realize are unique.
--
-- This will solve the word problem relatively fast, though it is not the
-- fastest known algorithm.
data BraidNF (n :: Nat)
BraidNF :: !Int -> [Permutation] -> BraidNF
-- | the exponent of Delta
[_nfDeltaExp] :: BraidNF -> !Int
-- | the permutations
[_nfPerms] :: BraidNF -> [Permutation]
-- | A braid word representing the given normal form
nfReprWord :: KnownNat n => BraidNF n -> Braid n
-- | Computes the normal form of a braid. We apply free reduction first, it
-- should be faster that way.
braidNormalForm :: KnownNat n => Braid n -> BraidNF n
-- | This function does not apply free reduction before computing the
-- normal form
braidNormalForm' :: KnownNat n => Braid n -> BraidNF n
-- | This one uses the naive inverse replacement method. Probably somewhat
-- slower than braidNormalForm'.
braidNormalFormNaive' :: KnownNat n => Braid n -> BraidNF n
-- | The starting set of a positive braid P is the subset of
-- [1..n-1] defined by
--
--
-- S(P) = [ i | P = sigma_i * Q , Q is positive ] = [ i | (sigma_i^-1 * P) is positive ]
--
--
-- This function returns the starting set a positive word, assuming it is
-- a permutation braid (see Lemma 2.4 in [2])
permWordStartingSet :: Int -> [Int] -> [Int]
-- | The finishing set of a positive braid P is the subset of
-- [1..n-1] defined by
--
--
-- F(P) = [ i | P = Q * sigma_i , Q is positive ] = [ i | (P * sigma_i^-1) is positive ]
--
--
-- This function returns the finishing set, assuming the input is a
-- permutation braid
permWordFinishingSet :: Int -> [Int] -> [Int]
-- | This satisfies
--
--
-- permutationStartingSet p == permWordStartingSet n (_permutationBraid p)
--
permutationStartingSet :: Permutation -> [Int]
-- | This satisfies
--
--
-- permutationFinishingSet p == permWordFinishingSet n (_permutationBraid p)
--
permutationFinishingSet :: Permutation -> [Int]
instance GHC.Show.Show Math.Combinat.Groups.Braid.NF.XGen
instance GHC.Classes.Eq Math.Combinat.Groups.Braid.NF.XGen
instance GHC.Show.Show (Math.Combinat.Groups.Braid.NF.BraidNF n)
instance GHC.Classes.Ord (Math.Combinat.Groups.Braid.NF.BraidNF n)
instance GHC.Classes.Eq (Math.Combinat.Groups.Braid.NF.BraidNF n)
-- | Skew partitions.
--
-- Skew partitions are the difference of two integer partitions, denoted
-- by lambda/mu.
--
-- For example
--
--
-- mkSkewPartition (Partition [9,7,3,2,2,1] , Partition [5,3,2,1])
--
--
-- creates the skew partition (9,7,3,2,2,1) / (5,3,2,1), which
-- looks like
--
module Math.Combinat.Partitions.Skew
-- | A skew partition lambda/mu is internally represented by the
-- list [ (mu_i , lambda_i-mu_i) | i<-[1..n] ]
newtype SkewPartition
SkewPartition :: [(Int, Int)] -> SkewPartition
-- | mkSkewPartition (lambda,mu) creates the skew partition
-- lambda/mu. Throws an error if mu is not a
-- sub-partition of lambda.
mkSkewPartition :: (Partition, Partition) -> SkewPartition
-- | Returns Nothing if mu is not a sub-partition of
-- lambda.
safeSkewPartition :: (Partition, Partition) -> Maybe SkewPartition
-- | The weight of a skew partition is the weight of the outer partition
-- minus the the weight of the inner partition (that is, the number of
-- boxes present).
skewPartitionWeight :: SkewPartition -> Int
-- | This function "cuts off" the "uninteresting parts" of a skew partition
normalizeSkewPartition :: SkewPartition -> SkewPartition
-- | Returns the outer and inner partition of a skew partition,
-- respectively:
--
--
-- mkSkewPartition . fromSkewPartition == id
--
fromSkewPartition :: SkewPartition -> (Partition, Partition)
-- | The lambda part of lambda/mu
outerPartition :: SkewPartition -> Partition
-- | The mu part of lambda/mu
innerPartition :: SkewPartition -> Partition
-- | The dual skew partition (that is, the mirror image to the main
-- diagonal)
dualSkewPartition :: SkewPartition -> SkewPartition
-- | Lists all skew partitions with the given outer shape and given (skew)
-- weight
skewPartitionsWithOuterShape :: Partition -> Int -> [SkewPartition]
-- | Lists all skew partitions with the given outer shape and any (skew)
-- weight
allSkewPartitionsWithOuterShape :: Partition -> [SkewPartition]
-- | Lists all skew partitions with the given inner shape and given (skew)
-- weight
skewPartitionsWithInnerShape :: Partition -> Int -> [SkewPartition]
asciiSkewFerrersDiagram :: SkewPartition -> ASCII
asciiSkewFerrersDiagram' :: (Char, Char) -> PartitionConvention -> SkewPartition -> ASCII
instance GHC.Show.Show Math.Combinat.Partitions.Skew.SkewPartition
instance GHC.Classes.Ord Math.Combinat.Partitions.Skew.SkewPartition
instance GHC.Classes.Eq Math.Combinat.Partitions.Skew.SkewPartition
instance Math.Combinat.Classes.HasWeight Math.Combinat.Partitions.Skew.SkewPartition
instance Math.Combinat.Classes.HasDuality Math.Combinat.Partitions.Skew.SkewPartition
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Partitions.Skew.SkewPartition
-- | Skew tableaux are skew partitions filled with numbers.
--
-- For example:
--
module Math.Combinat.Tableaux.Skew
-- | A skew tableau is represented by a list of offsets and entries
newtype SkewTableau a
SkewTableau :: [(Int, [a])] -> SkewTableau a
-- | The shape of a skew tableau
skewTableauShape :: SkewTableau a -> SkewPartition
-- | The weight of a tableau is the weight of its shape, or the number of
-- entries
skewTableauWeight :: SkewTableau a -> Int
-- | The dual of a skew tableau, that is, its mirror image to the main
-- diagonal
dualSkewTableau :: forall a. SkewTableau a -> SkewTableau a
-- | A tableau is semistandard if its entries are weekly increasing
-- horizontally and strictly increasing vertically
isSemiStandardSkewTableau :: SkewTableau Int -> Bool
-- | A tableau is standard if it is semistandard and its content is
-- exactly [1..n], where n is the weight.
isStandardSkewTableau :: SkewTableau Int -> Bool
-- | All semi-standard skew tableaux filled with the numbers
-- [1..n]
semiStandardSkewTableaux :: Int -> SkewPartition -> [SkewTableau Int]
-- | ASCII drawing of a skew tableau (using the English notation)
asciiSkewTableau :: Show a => SkewTableau a -> ASCII
asciiSkewTableau' :: Show a => String -> PartitionConvention -> SkewTableau a -> ASCII
-- | The reversed (right-to-left) rows, concatenated
skewTableauRowWord :: SkewTableau a -> [a]
-- | The reversed (bottom-to-top) columns, concatenated
skewTableauColumnWord :: SkewTableau a -> [a]
-- | Fills a skew partition with content, in row word order
fillSkewPartitionWithRowWord :: SkewPartition -> [a] -> SkewTableau a
-- | Fills a skew partition with content, in column word order
fillSkewPartitionWithColumnWord :: SkewPartition -> [a] -> SkewTableau a
-- | If the skew tableau's row word is a lattice word, we can make a
-- partition from its content
skewTableauRowContent :: SkewTableau Int -> Maybe Partition
instance GHC.Show.Show a => GHC.Show.Show (Math.Combinat.Tableaux.Skew.SkewTableau a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.Combinat.Tableaux.Skew.SkewTableau a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Combinat.Tableaux.Skew.SkewTableau a)
instance GHC.Base.Functor Math.Combinat.Tableaux.Skew.SkewTableau
instance Math.Combinat.Classes.HasShape (Math.Combinat.Tableaux.Skew.SkewTableau a) Math.Combinat.Partitions.Skew.SkewPartition
instance Math.Combinat.Classes.HasWeight (Math.Combinat.Tableaux.Skew.SkewTableau a)
instance Math.Combinat.Classes.HasDuality (Math.Combinat.Tableaux.Skew.SkewTableau a)
instance GHC.Show.Show a => Math.Combinat.ASCII.DrawASCII (Math.Combinat.Tableaux.Skew.SkewTableau a)
-- | Gelfand-Tsetlin patterns and Kostka numbers.
--
-- Gelfand-Tsetlin patterns (or tableaux) are triangular arrays like
--
--
-- [ 3 ]
-- [ 3 , 2 ]
-- [ 3 , 1 , 0 ]
-- [ 2 , 0 , 0 , 0 ]
--
--
-- with both rows and columns non-increasing non-negative integers. Note:
-- these are in bijection with the semi-standard Young tableaux.
--
-- If we add the further restriction that the top diagonal reads
-- lambda, and the diagonal sums are partial sums of
-- mu, where lambda and mu are two partitions
-- (in this case lambda=[3,2] and mu=[2,1,1,1]), then
-- the number of the resulting patterns or tableaux is the Kostka number
-- K(lambda,mu). Actually mu doesn't even need to the
-- be non-increasing.
module Math.Combinat.Tableaux.GelfandTsetlin
-- | Kostka numbers (via counting Gelfand-Tsetlin patterns). See for
-- example http://en.wikipedia.org/wiki/Kostka_number
--
-- K(lambda,mu)==0 unless lambda dominates mu:
--
--
-- [ mu | mu <- partitions (weight lam) , kostkaNumber lam mu > 0 ] == dominatedPartitions lam
--
kostkaNumber :: Partition -> Partition -> Int
-- | Very naive (and slow) implementation of Kostka numbers, for reference.
kostkaNumberReferenceNaive :: Partition -> Partition -> Int
-- | Lists all (positive) Kostka numbers K(lambda,mu) with the
-- given lambda:
--
--
-- kostkaNumbersWithGivenLambda lambda == Map.fromList [ (mu , kostkaNumber lambda mu) | mu <- dominatedPartitions lambda ]
--
--
-- It's much faster than computing the individual Kostka numbers, but not
-- as fast as it could be.
kostkaNumbersWithGivenLambda :: forall coeff. Num coeff => Partition -> Map Partition coeff
-- | Lists all (positive) Kostka numbers K(lambda,mu) with the
-- given mu:
--
--
-- kostkaNumbersWithGivenMu mu == Map.fromList [ (lambda , kostkaNumber lambda mu) | lambda <- dominatingPartitions mu ]
--
--
-- This function uses the iterated Pieri rule, and is relatively fast.
kostkaNumbersWithGivenMu :: Partition -> Map Partition Int
-- | A Gelfand-Tstetlin tableau
type GT = [[Int]]
asciiGT :: GT -> ASCII
kostkaGelfandTsetlinPatterns :: Partition -> Partition -> [GT]
-- | Generates all Kostka-Gelfand-Tsetlin tableau, that is, triangular
-- arrays like
--
--
-- [ 3 ]
-- [ 3 , 2 ]
-- [ 3 , 1 , 0 ]
-- [ 2 , 0 , 0 , 0 ]
--
--
-- with both rows and column non-increasing such that the top diagonal
-- read lambda (in this case lambda=[3,2]) and the diagonal sums
-- are partial sums of mu (in this case mu=[2,1,1,1])
--
-- The number of such GT tableaux is the Kostka number K(lambda,mu).
kostkaGelfandTsetlinPatterns' :: Partition -> [Int] -> [GT]
-- | This returns the corresponding Kostka number:
--
--
-- countKostkaGelfandTsetlinPatterns lambda mu == length (kostkaGelfandTsetlinPatterns lambda mu)
--
countKostkaGelfandTsetlinPatterns :: Partition -> Partition -> Int
-- | Computes the Schur expansion of h[n1]*h[n2]*h[n3]*...*h[nk]
-- via iterating the Pieri rule. Note: the coefficients are actually the
-- Kostka numbers; the following is true:
--
--
-- Map.toList (iteratedPieriRule (fromPartition mu)) == [ (lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]
--
--
-- This should be faster than individually computing all these Kostka
-- numbers.
iteratedPieriRule :: Num coeff => [Int] -> Map Partition coeff
-- | Iterating the Pieri rule, we can compute the Schur expansion of
-- h[lambda]*h[n1]*h[n2]*h[n3]*...*h[nk]
iteratedPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff
iteratedPieriRule'' :: Num coeff => (Partition, coeff) -> [Int] -> Map Partition coeff
-- | Computes the Schur expansion of e[n1]*e[n2]*e[n3]*...*e[nk]
-- via iterating the Pieri rule. Note: the coefficients are actually the
-- Kostka numbers; the following is true:
--
--
-- Map.toList (iteratedDualPieriRule (fromPartition mu)) ==
-- [ (dualPartition lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]
--
--
-- This should be faster than individually computing all these Kostka
-- numbers. It is a tiny bit slower than iteratedPieriRule.
iteratedDualPieriRule :: Num coeff => [Int] -> Map Partition coeff
-- | Iterating the Pieri rule, we can compute the Schur expansion of
-- e[lambda]*e[n1]*e[n2]*e[n3]*...*e[nk]
iteratedDualPieriRule' :: Num coeff => Partition -> [Int] -> Map Partition coeff
iteratedDualPieriRule'' :: Num coeff => (Partition, coeff) -> [Int] -> Map Partition coeff
-- | The Littlewood-Richardson rule
module Math.Combinat.Tableaux.LittlewoodRichardson
-- | lrCoeff lam (mu,nu) computes the coressponding
-- Littlewood-Richardson coefficients. This is also the coefficient of
-- s[lambda] in the product s[mu]*s[nu]
--
-- Note: This is much slower than using lrRule or lrMult to
-- compute several coefficients at the same time!
lrCoeff :: Partition -> (Partition, Partition) -> Int
-- | lrCoeff (lam/nu) mu computes the coressponding
-- Littlewood-Richardson coefficients. This is also the coefficient of
-- s[mu] in the product s[lam/nu]
--
-- Note: This is much slower than using lrRule or lrMult to
-- compute several coefficients at the same time!
lrCoeff' :: SkewPartition -> Partition -> Int
-- | Computes the expansion of the product of Schur polynomials
-- s[mu]*s[nu] using the Littlewood-Richardson rule. Note: this
-- is symmetric in the two arguments.
--
-- Based on the wikipedia article
-- https://en.wikipedia.org/wiki/Littlewood-Richardson_rule
--
--
-- lrMult mu nu == Map.fromList list where
-- lamw = weight nu + weight mu
-- list = [ (lambda, coeff)
-- | lambda <- partitions lamw
-- , let coeff = lrCoeff lambda (mu,nu)
-- , coeff /= 0
-- ]
--
lrMult :: Partition -> Partition -> Map Partition Int
-- | lrRule computes the expansion of a skew Schur function
-- s[lambda/mu] via the Littlewood-Richardson rule.
--
-- Adapted from John Stembridge's Maple code:
-- http://www.math.lsa.umich.edu/~jrs/software/SFexamples/LR_rule
--
--
-- lrRule (mkSkewPartition (lambda,nu)) == Map.fromList list where
-- muw = weight lambda - weight nu
-- list = [ (mu, coeff)
-- | mu <- partitions muw
-- , let coeff = lrCoeff lambda (mu,nu)
-- , coeff /= 0
-- ]
--
lrRule :: SkewPartition -> Map Partition Int
-- | _lrRule lambda mu computes the expansion of the skew Schur
-- function s[lambda/mu] via the Littlewood-Richardson rule.
_lrRule :: Partition -> Partition -> Map Partition Int
-- | Naive (very slow) reference implementation of the
-- Littlewood-Richardson rule, based on the definition "count the
-- semistandard skew tableaux whose row content is a lattice word"
lrRuleNaive :: SkewPartition -> Map Partition Int
-- | lrScalar (lambda/mu) (alpha/beta) computes the scalar product
-- of the two skew Schur functions s[lambda/mu] and
-- s[alpha/beta] via the Littlewood-Richardson rule.
--
-- Adapted from John Stembridge Maple code:
-- http://www.math.lsa.umich.edu/~jrs/software/SFexamples/LR_rule
lrScalar :: SkewPartition -> SkewPartition -> Int
_lrScalar :: (Partition, Partition) -> (Partition, Partition) -> Int
-- | Binary trees, forests, etc. See: Donald E. Knuth: The Art of Computer
-- Programming, vol 4, pre-fascicle 4A.
--
-- For example, here are all the binary trees on 4 nodes:
--
module Math.Combinat.Trees.Binary
-- | A binary tree with leaves decorated with type a.
data BinTree a
Branch :: (BinTree a) -> (BinTree a) -> BinTree a
Leaf :: a -> BinTree a
leaf :: BinTree ()
-- | The monadic join operation of binary trees
graft :: BinTree (BinTree a) -> BinTree a
-- | A binary tree with leaves and internal nodes decorated with types
-- a and b, respectively.
data BinTree' a b
Branch' :: (BinTree' a b) -> b -> (BinTree' a b) -> BinTree' a b
Leaf' :: a -> BinTree' a b
forgetNodeDecorations :: BinTree' a b -> BinTree a
data Paren
LeftParen :: Paren
RightParen :: Paren
parenthesesToString :: [Paren] -> String
stringToParentheses :: String -> [Paren]
numberOfNodes :: HasNumberOfNodes t => t -> Int
numberOfLeaves :: HasNumberOfLeaves t => t -> Int
-- | Convert a binary tree to a rose tree (from Data.Tree)
toRoseTree :: BinTree a -> Tree (Maybe a)
toRoseTree' :: BinTree' a b -> Tree (Either b a)
-- | Enumerates the leaves a tree, starting from 0, ignoring old labels
enumerateLeaves_ :: BinTree a -> BinTree Int
-- | Enumerates the leaves a tree, starting from zero
enumerateLeaves :: BinTree a -> BinTree (a, Int)
-- | Enumerates the leaves a tree, starting from zero, and also returns the
-- number of leaves
enumerateLeaves' :: BinTree a -> (Int, BinTree (a, Int))
-- | Generates all sequences of nested parentheses of length 2n in
-- lexigraphic order.
--
-- Synonym for fasc4A_algorithm_P.
nestedParentheses :: Int -> [[Paren]]
-- | Synonym for fasc4A_algorithm_W.
randomNestedParentheses :: RandomGen g => Int -> g -> ([Paren], g)
-- | Synonym for fasc4A_algorithm_U.
nthNestedParentheses :: Int -> Integer -> [Paren]
countNestedParentheses :: Int -> Integer
-- | Generates all sequences of nested parentheses of length 2n. Order is
-- lexicographical (when right parentheses are considered smaller then
-- left ones). Based on "Algorithm P" in Knuth, but less efficient
-- because of the "idiomatic" code.
fasc4A_algorithm_P :: Int -> [[Paren]]
-- | Generates a uniformly random sequence of nested parentheses of length
-- 2n. Based on "Algorithm W" in Knuth.
fasc4A_algorithm_W :: RandomGen g => Int -> g -> ([Paren], g)
-- | Nth sequence of nested parentheses of length 2n. The order is the same
-- as in fasc4A_algorithm_P. Based on "Algorithm U" in Knuth.
fasc4A_algorithm_U :: Int -> Integer -> [Paren]
-- | Generates all binary trees with n nodes. At the moment just a
-- synonym for binaryTreesNaive.
binaryTrees :: Int -> [BinTree ()]
-- | # = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }.
--
-- This is also the counting function for forests and nested parentheses.
countBinaryTrees :: Int -> Integer
-- | Generates all binary trees with n nodes. The naive algorithm.
binaryTreesNaive :: Int -> [BinTree ()]
-- | Generates an uniformly random binary tree, using
-- fasc4A_algorithm_R.
randomBinaryTree :: RandomGen g => Int -> g -> (BinTree (), g)
-- | Grows a uniformly random binary tree. "Algorithm R" (Remy's procudere)
-- in Knuth. Nodes are decorated with odd numbers, leaves with even
-- numbers (from the set [0..2n]). Uses mutable arrays
-- internally.
fasc4A_algorithm_R :: RandomGen g => Int -> g -> (BinTree' Int Int, g)
-- | Draws a binary tree in ASCII, ignoring node labels.
--
-- Example:
--
--
-- autoTabulate RowMajor (Right 5) $ map asciiBinaryTree_ $ binaryTrees 4
--
asciiBinaryTree_ :: BinTree a -> ASCII
type Dot = String
graphvizDotBinTree :: Show a => String -> BinTree a -> Dot
graphvizDotBinTree' :: (Show a, Show b) => String -> BinTree' a b -> Dot
-- | Generates graphviz .dot file from a forest. The first
-- argument tells whether to make the individual trees clustered
-- subgraphs; the second is the name of the graph.
graphvizDotForest :: Show a => Bool -> Bool -> String -> Forest a -> Dot
-- | Generates graphviz .dot file from a tree. The first argument
-- is the name of the graph.
graphvizDotTree :: Show a => Bool -> String -> Tree a -> Dot
forestToNestedParentheses :: Forest a -> [Paren]
forestToBinaryTree :: Forest a -> BinTree ()
nestedParenthesesToForest :: [Paren] -> Maybe (Forest ())
nestedParenthesesToForestUnsafe :: [Paren] -> Forest ()
nestedParenthesesToBinaryTree :: [Paren] -> Maybe (BinTree ())
nestedParenthesesToBinaryTreeUnsafe :: [Paren] -> BinTree ()
binaryTreeToForest :: BinTree a -> Forest ()
binaryTreeToNestedParentheses :: BinTree a -> [Paren]
instance GHC.Read.Read Math.Combinat.Trees.Binary.Paren
instance GHC.Show.Show Math.Combinat.Trees.Binary.Paren
instance GHC.Classes.Ord Math.Combinat.Trees.Binary.Paren
instance GHC.Classes.Eq Math.Combinat.Trees.Binary.Paren
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (Math.Combinat.Trees.Binary.BinTree' a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Math.Combinat.Trees.Binary.BinTree' a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Math.Combinat.Trees.Binary.BinTree' a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Math.Combinat.Trees.Binary.BinTree' a b)
instance GHC.Read.Read a => GHC.Read.Read (Math.Combinat.Trees.Binary.BinTree a)
instance GHC.Show.Show a => GHC.Show.Show (Math.Combinat.Trees.Binary.BinTree a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.Combinat.Trees.Binary.BinTree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Combinat.Trees.Binary.BinTree a)
instance Math.Combinat.Classes.HasNumberOfNodes (Math.Combinat.Trees.Binary.BinTree a)
instance Math.Combinat.Classes.HasNumberOfLeaves (Math.Combinat.Trees.Binary.BinTree a)
instance Math.Combinat.Classes.HasNumberOfNodes (Math.Combinat.Trees.Binary.BinTree' a b)
instance Math.Combinat.Classes.HasNumberOfLeaves (Math.Combinat.Trees.Binary.BinTree' a b)
instance GHC.Base.Functor Math.Combinat.Trees.Binary.BinTree
instance Data.Foldable.Foldable Math.Combinat.Trees.Binary.BinTree
instance Data.Traversable.Traversable Math.Combinat.Trees.Binary.BinTree
instance GHC.Base.Applicative Math.Combinat.Trees.Binary.BinTree
instance GHC.Base.Monad Math.Combinat.Trees.Binary.BinTree
instance Math.Combinat.ASCII.DrawASCII (Math.Combinat.Trees.Binary.BinTree ())
-- | Dyck paths, lattice paths, etc
--
-- For example, the following figure represents a Dyck path of height 5
-- with 3 zero-touches (not counting the starting point, but counting the
-- endpoint) and 7 peaks:
--
module Math.Combinat.LatticePaths
-- | A step in a lattice path
data Step
-- | the step (1,1)
UpStep :: Step
-- | the step (1,-1)
DownStep :: Step
-- | A lattice path is a path using only the allowed steps, never going
-- below the zero level line y=0.
--
-- Note that if you rotate such a path by 45 degrees counterclockwise,
-- you get a path which uses only the steps (1,0) and
-- (0,1), and stays above the main diagonal (hence the name, we
-- just use a different convention).
type LatticePath = [Step]
-- | Draws the path into a list of lines. For example try:
--
--
-- autotabulate RowMajor (Right 5) (map asciiPath $ dyckPaths 4)
--
asciiPath :: LatticePath -> ASCII
-- | A lattice path is called "valid", if it never goes below the
-- y=0 line.
isValidPath :: LatticePath -> Bool
-- | A Dyck path is a lattice path whose last point lies on the
-- y=0 line
isDyckPath :: LatticePath -> Bool
-- | Maximal height of a lattice path
pathHeight :: LatticePath -> Int
-- | Endpoint of a lattice path, which starts from (0,0).
pathEndpoint :: LatticePath -> (Int, Int)
-- | Returns the coordinates of the path (excluding the starting point
-- (0,0), but including the endpoint)
pathCoordinates :: LatticePath -> [(Int, Int)]
-- | Counts the up-steps
pathNumberOfUpSteps :: LatticePath -> Int
-- | Counts the down-steps
pathNumberOfDownSteps :: LatticePath -> Int
-- | Counts both the up-steps and down-steps
pathNumberOfUpDownSteps :: LatticePath -> (Int, Int)
-- | Number of peaks of a path (excluding the endpoint)
pathNumberOfPeaks :: LatticePath -> Int
-- | Number of points on the path which touch the y=0 zero level
-- line (excluding the starting point (0,0), but including the
-- endpoint; that is, for Dyck paths it this is always positive!).
pathNumberOfZeroTouches :: LatticePath -> Int
-- | Number of points on the path which touch the level line at height
-- h (excluding the starting point (0,0), but including
-- the endpoint).
pathNumberOfTouches' :: Int -> LatticePath -> Int
-- | dyckPaths m lists all Dyck paths from (0,0) to
-- (2m,0).
--
-- Remark: Dyck paths are obviously in bijection with nested parentheses,
-- and thus also with binary trees.
--
-- Order is reverse lexicographical:
--
--
-- sort (dyckPaths m) == reverse (dyckPaths m)
--
dyckPaths :: Int -> [LatticePath]
-- | dyckPaths m lists all Dyck paths from (0,0) to
-- (2m,0).
--
--
-- sort (dyckPathsNaive m) == sort (dyckPaths m)
--
--
-- Naive recursive algorithm, order is ad-hoc
dyckPathsNaive :: Int -> [LatticePath]
-- | The number of Dyck paths from (0,0) to (2m,0) is
-- simply the m'th Catalan number.
countDyckPaths :: Int -> Integer
-- | The trivial bijection
nestedParensToDyckPath :: [Paren] -> LatticePath
-- | The trivial bijection in the other direction
dyckPathToNestedParens :: LatticePath -> [Paren]
-- | boundedDyckPaths h m lists all Dyck paths from (0,0)
-- to (2m,0) whose height is at most h. Synonym for
-- boundedDyckPathsNaive.
boundedDyckPaths :: Int -> Int -> [LatticePath]
-- | boundedDyckPathsNaive h m lists all Dyck paths from
-- (0,0) to (2m,0) whose height is at most h.
--
--
-- sort (boundedDyckPaths h m) == sort [ p | p <- dyckPaths m , pathHeight p <= h ]
-- sort (boundedDyckPaths m m) == sort (dyckPaths m)
--
--
-- Naive recursive algorithm, resulting order is pretty ad-hoc.
boundedDyckPathsNaive :: Int -> Int -> [LatticePath]
-- | All lattice paths from (0,0) to (x,y). Clearly empty
-- unless x-y is even. Synonym for latticePathsNaive
latticePaths :: (Int, Int) -> [LatticePath]
-- | All lattice paths from (0,0) to (x,y). Clearly empty
-- unless x-y is even.
--
-- Note that
--
--
-- sort (dyckPaths n) == sort (latticePaths (0,2*n))
--
--
-- Naive recursive algorithm, resulting order is pretty ad-hoc.
latticePathsNaive :: (Int, Int) -> [LatticePath]
-- | Lattice paths are counted by the numbers in the Catalan triangle.
countLatticePaths :: (Int, Int) -> Integer
-- | touchingDyckPaths k m lists all Dyck paths from
-- (0,0) to (2m,0) which touch the zero level line
-- y=0 exactly k times (excluding the starting point,
-- but including the endpoint; thus, k should be positive).
-- Synonym for touchingDyckPathsNaive.
touchingDyckPaths :: Int -> Int -> [LatticePath]
-- | touchingDyckPathsNaive k m lists all Dyck paths from
-- (0,0) to (2m,0) which touch the zero level line
-- y=0 exactly k times (excluding the starting point,
-- but including the endpoint; thus, k should be positive).
--
--
-- sort (touchingDyckPathsNaive k m) == sort [ p | p <- dyckPaths m , pathNumberOfZeroTouches p == k ]
--
--
-- Naive recursive algorithm, resulting order is pretty ad-hoc.
touchingDyckPathsNaive :: Int -> Int -> [LatticePath]
-- | There is a bijection from the set of non-empty Dyck paths of length
-- 2n which touch the zero lines t times, to lattice
-- paths from (0,0) to (2n-t-1,t-1) (just remove all
-- the down-steps just before touching the zero line, and also the very
-- first up-step). This gives us a counting formula.
countTouchingDyckPaths :: Int -> Int -> Integer
-- | peakingDyckPaths k m lists all Dyck paths from (0,0)
-- to (2m,0) with exactly k peaks.
--
-- Synonym for peakingDyckPathsNaive
peakingDyckPaths :: Int -> Int -> [LatticePath]
-- | peakingDyckPathsNaive k m lists all Dyck paths from
-- (0,0) to (2m,0) with exactly k peaks.
--
--
-- sort (peakingDyckPathsNaive k m) = sort [ p | p <- dyckPaths m , pathNumberOfPeaks p == k ]
--
--
-- Naive recursive algorithm, resulting order is pretty ad-hoc.
peakingDyckPathsNaive :: Int -> Int -> [LatticePath]
-- | Dyck paths of length 2m with k peaks are counted by
-- the Narayana numbers N(m,k) = binom{m}{k} binom{m}{k-1} / m
countPeakingDyckPaths :: Int -> Int -> Integer
-- | A uniformly random Dyck path of length 2m
randomDyckPath :: RandomGen g => Int -> g -> (LatticePath, g)
instance GHC.Show.Show Math.Combinat.LatticePaths.Step
instance GHC.Classes.Ord Math.Combinat.LatticePaths.Step
instance GHC.Classes.Eq Math.Combinat.LatticePaths.Step
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.LatticePaths.LatticePath
instance Math.Combinat.Classes.HasHeight Math.Combinat.LatticePaths.LatticePath
instance Math.Combinat.Classes.HasWidth Math.Combinat.LatticePaths.LatticePath
-- | Thompson's group F.
--
-- See eg. https://en.wikipedia.org/wiki/Thompson_groups
--
-- Based mainly on James Michael Belk's PhD thesis "THOMPSON'S GROUP F";
-- see http://www.math.u-psud.fr/~breuilla/Belk.pdf
module Math.Combinat.Groups.Thompson.F
-- | A tree diagram, consisting of two binary trees with the same number of
-- leaves, representing an element of the group F.
data TDiag
TDiag :: !Int -> !T -> !T -> TDiag
-- | the width is the number of leaves, minus 1, of both diagrams
[_width] :: TDiag -> !Int
-- | the top diagram correspond to the domain
[_domain] :: TDiag -> !T
-- | the bottom diagram corresponds to the range
[_range] :: TDiag -> !T
-- | Creates a tree diagram from two trees
mkTDiag :: T -> T -> TDiag
-- | Creates a tree diagram, but does not reduce it.
mkTDiagDontReduce :: T -> T -> TDiag
isValidTDiag :: TDiag -> Bool
isPositive :: TDiag -> Bool
isReduced :: TDiag -> Bool
-- | The generator x0
x0 :: TDiag
-- | The generator x1
x1 :: TDiag
-- | The generators x0, x1, x2 ...
xk :: Int -> TDiag
-- | The identity element in the group F
identity :: TDiag
-- | A positive diagram is a diagram whose bottom tree (the range)
-- is a right vine.
positive :: T -> TDiag
-- | Swaps the top and bottom of a tree diagram. This is the inverse in the
-- group F. (Note: we don't do reduction here, as this operation keeps
-- the reducedness)
inverse :: TDiag -> TDiag
-- | Decides whether two (possibly unreduced) tree diagrams represents the
-- same group element in F.
equivalent :: TDiag -> TDiag -> Bool
-- | Reduces a diagram. The result is a normal form of an element in the
-- group F.
reduce :: TDiag -> TDiag
-- | List of carets at the bottom of the tree, indexed by their left edge
-- position
treeCaretList :: T -> [Int]
-- | Remove the carets with the given indices (throws an error if there is
-- no caret at the given index)
removeCarets :: [Int] -> T -> T
-- | If diag1 corresponds to the PL function f, and
-- diag2 to g, then compose diag1 diag2 will
-- correspond to (g.f) (note that the order is opposite than
-- normal function composition!)
--
-- This is the multiplication in the group F.
compose :: TDiag -> TDiag -> TDiag
-- | Compose two tree diagrams without reducing the result
composeDontReduce :: TDiag -> TDiag -> TDiag
-- | Given two binary trees, we return a pair of list of subtrees which,
-- grafted the to leaves of the first (resp. the second) tree, results in
-- the same extended tree.
extensionToCommonTree :: T -> T -> ([T], [T])
-- | Returns the list of dyadic subdivision points
subdivision1 :: T -> [Rational]
-- | Returns the list of dyadic intervals
subdivision2 :: T -> [(Rational, Rational)]
-- | A (strict) binary tree with labelled leaves (but unlabelled nodes)
data Tree a
Branch :: !(Tree a) -> !(Tree a) -> Tree a
Leaf :: !a -> Tree a
-- | The monadic join operation of binary trees
graft :: Tree (Tree a) -> Tree a
-- | A list version of graft
listGraft :: [Tree a] -> Tree b -> Tree a
-- | A completely unlabelled binary tree
type T = Tree ()
leaf :: T
branch :: T -> T -> T
caret :: T
treeNumberOfLeaves :: Tree a -> Int
-- | The width of the tree is the number of leaves minus 1.
treeWidth :: Tree a -> Int
-- | Enumerates the leaves a tree, starting from 0
enumerate_ :: Tree a -> Tree Int
-- | Enumerates the leaves a tree, and also returns the number of leaves
enumerate :: Tree a -> (Int, Tree Int)
-- | "Right vine" of the given width
rightVine :: Int -> T
-- | "Left vine" of the given width
leftVine :: Int -> T
-- | Flips each node of a binary tree
flipTree :: Tree a -> Tree a
-- | Tree and BinTree are the same type, except that
-- Tree is strict.
--
-- TODO: maybe unify these two types? Until that, you can convert between
-- the two with these functions if necessary.
toBinTree :: Tree a -> BinTree a
fromBinTree :: BinTree a -> Tree a
-- | Draws a binary tree, with all leaves at the same (bottom) row
asciiT :: T -> ASCII
-- | Draws a binary tree; when the boolean flag is True, we draw
-- upside down
asciiT' :: Bool -> T -> ASCII
-- | Draws a binary tree, with all leaves at the same (bottom) row, and
-- labelling the leaves starting with 0 (continuing with letters after 9)
asciiTLabels :: T -> ASCII
-- | When the flag is true, we draw upside down
asciiTLabels' :: Bool -> T -> ASCII
-- | Draws a tree diagram
asciiTDiag :: TDiag -> ASCII
instance GHC.Show.Show Math.Combinat.Groups.Thompson.F.TDiag
instance GHC.Classes.Ord Math.Combinat.Groups.Thompson.F.TDiag
instance GHC.Classes.Eq Math.Combinat.Groups.Thompson.F.TDiag
instance GHC.Base.Functor Math.Combinat.Groups.Thompson.F.Tree
instance GHC.Show.Show a => GHC.Show.Show (Math.Combinat.Groups.Thompson.F.Tree a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.Combinat.Groups.Thompson.F.Tree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.Combinat.Groups.Thompson.F.Tree a)
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Groups.Thompson.F.TDiag
instance Math.Combinat.Classes.HasWidth Math.Combinat.Groups.Thompson.F.TDiag
instance Math.Combinat.ASCII.DrawASCII Math.Combinat.Groups.Thompson.F.T
instance Math.Combinat.Classes.HasNumberOfLeaves (Math.Combinat.Groups.Thompson.F.Tree a)
instance Math.Combinat.Classes.HasWidth (Math.Combinat.Groups.Thompson.F.Tree a)
-- | Words in free groups (and free powers of cyclic groups).
--
-- This module is not re-exported by Math.Combinat
module Math.Combinat.Groups.Free
-- | A generator of a (free) group, indexed by which "copy" of the group we
-- are dealing with.
data Generator idx
Gen :: !idx -> Generator idx
Inv :: !idx -> Generator idx
-- | The index of a generator
genIdx :: Generator idx -> idx
-- | The sign of the (exponent of the) generator (that is, the generator is
-- Plus, the inverse is Minus)
genSign :: Generator idx -> Sign
genSignValue :: Generator idx -> Int
-- | keep the index, but return always the Gen one.
absGen :: Generator idx -> Generator idx
-- | A word, describing (non-uniquely) an element of a group. The
-- identity element is represented (among others) by the empty word.
type Word idx = [Generator idx]
-- | Generators are shown as small letters: a, b,
-- c, ... and their inverses are shown as capital letters, so
-- A=a^-1, B=b^-1, etc.
showGen :: Generator Int -> Char
showWord :: Word Int -> String
-- | The inverse of a generator
inverseGen :: Generator a -> Generator a
-- | The inverse of a word
inverseWord :: Word a -> Word a
-- | Lists all words of the given length (total number will be
-- (2g)^n). The numbering of the generators is [1..g].
allWords :: Int -> Int -> [Word Int]
-- | Lists all words of the given length which do not contain inverse
-- generators (total number will be g^n). The numbering of the
-- generators is [1..g].
allWordsNoInv :: Int -> Int -> [Word Int]
-- | A random group generator (or its inverse) between 1 and
-- g
randomGenerator :: RandomGen g => Int -> g -> (Generator Int, g)
-- | A random group generator (but never its inverse) between 1
-- and g
randomGeneratorNoInv :: RandomGen g => Int -> g -> (Generator Int, g)
-- | A random word of length n using g generators (or
-- their inverses)
randomWord :: RandomGen g => Int -> Int -> g -> (Word Int, g)
-- | A random word of length n using g generators (but
-- not their inverses)
randomWordNoInv :: RandomGen g => Int -> Int -> g -> (Word Int, g)
-- | Multiplication of the free group (returns the reduced result). It is
-- true for any two words w1 and w2 that
--
--
-- multiplyFree (reduceWordFree w1) (reduceWord w2) = multiplyFree w1 w2
--
multiplyFree :: Eq idx => Word idx -> Word idx -> Word idx
-- | Decides whether two words represent the same group element in the free
-- group
equivalentFree :: Eq idx => Word idx -> Word idx -> Bool
-- | Reduces a word in a free group by repeatedly removing
-- x*x^(-1) and x^(-1)*x pairs. The set of reduced
-- words forms the free group; the multiplication is obtained by
-- concatenation followed by reduction.
reduceWordFree :: Eq idx => Word idx -> Word idx
-- | Naive (but canonical) reduction algorithm for the free groups
reduceWordFreeNaive :: Eq idx => Word idx -> Word idx
-- | Counts the number of words of length n which reduce to the
-- identity element.
--
-- Generating function is Gf_g(u) = \frac {2g-1} { g-1 + g \sqrt{ 1 -
-- (8g-4)u^2 } }
countIdentityWordsFree :: Int -> Int -> Integer
-- | Counts the number of words of length n whose reduced form has
-- length k (clearly n and k must have the
-- same parity for this to be nonzero):
--
--
-- countWordReductionsFree g n k == sum [ 1 | w <- allWords g n, k == length (reduceWordFree w) ]
--
countWordReductionsFree :: Int -> Int -> Int -> Integer
-- | Multiplication in free products of Z2's
multiplyZ2 :: Eq idx => Word idx -> Word idx -> Word idx
-- | Multiplication in free products of Z3's
multiplyZ3 :: Eq idx => Word idx -> Word idx -> Word idx
-- | Multiplication in free products of Zm's
multiplyZm :: Eq idx => Int -> Word idx -> Word idx -> Word idx
-- | Decides whether two words represent the same group element in free
-- products of Z2
equivalentZ2 :: Eq idx => Word idx -> Word idx -> Bool
-- | Decides whether two words represent the same group element in free
-- products of Z3
equivalentZ3 :: Eq idx => Word idx -> Word idx -> Bool
-- | Decides whether two words represent the same group element in free
-- products of Zm
equivalentZm :: Eq idx => Int -> Word idx -> Word idx -> Bool
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^2=1 (that is, free products of Z2's)
reduceWordZ2 :: Eq idx => Word idx -> Word idx
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^3=1 (that is, free products of Z3's)
reduceWordZ3 :: Eq idx => Word idx -> Word idx
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^m=1 (that is, free products of Zm's)
reduceWordZm :: Eq idx => Int -> Word idx -> Word idx
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^2=1 (that is, free products of Z2's).
-- Naive (but canonical) algorithm.
reduceWordZ2Naive :: Eq idx => Word idx -> Word idx
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^3=1 (that is, free products of Z3's).
-- Naive (but canonical) algorithm.
reduceWordZ3Naive :: Eq idx => Word idx -> Word idx
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^m=1 (that is, free products of Zm's).
-- Naive (but canonical) algorithm.
reduceWordZmNaive :: Eq idx => Int -> Word idx -> Word idx
-- | Counts the number of words (without inverse generators) of length
-- n which reduce to the identity element, using the relations
-- x^2=1.
--
-- Generating function is Gf_g(u) = \frac {2g-2} { g-2 + g \sqrt{ 1 -
-- (4g-4)u^2 } }
--
-- The first few g cases:
--
--
-- A000984 = [ countIdentityWordsZ2 2 (2*n) | n<-[0..] ] = [1,2,6,20,70,252,924,3432,12870,48620,184756...]
-- A089022 = [ countIdentityWordsZ2 3 (2*n) | n<-[0..] ] = [1,3,15,87,543,3543,23823,163719,1143999,8099511,57959535...]
-- A035610 = [ countIdentityWordsZ2 4 (2*n) | n<-[0..] ] = [1,4,28,232,2092,19864,195352,1970896,20275660,211823800,2240795848...]
-- A130976 = [ countIdentityWordsZ2 5 (2*n) | n<-[0..] ] = [1,5,45,485,5725,71445,925965,12335685,167817405,2321105525,32536755565...]
--
countIdentityWordsZ2 :: Int -> Int -> Integer
-- | Counts the number of words (without inverse generators) of length
-- n whose reduced form in the product of Z2-s (that is, for
-- each generator x we have x^2=1) has length
-- k (clearly n and k must have the same
-- parity for this to be nonzero):
--
--
-- countWordReductionsZ2 g n k == sum [ 1 | w <- allWordsNoInv g n, k == length (reduceWordZ2 w) ]
--
countWordReductionsZ2 :: Int -> Int -> Int -> Integer
-- | Counts the number of words (without inverse generators) of length
-- n which reduce to the identity element, using the relations
-- x^3=1.
--
--
-- countIdentityWordsZ3NoInv g n == sum [ 1 | w <- allWordsNoInv g n, 0 == length (reduceWordZ2 w) ]
--
--
-- In mathematica, the formula is: Sum[ g^k * (g-1)^(n-k) * k/n *
-- Binomial[3*n-k-1, n-k] , {k, 1,n} ]
countIdentityWordsZ3NoInv :: Int -> Int -> Integer
instance GHC.Read.Read idx => GHC.Read.Read (Math.Combinat.Groups.Free.Generator idx)
instance GHC.Show.Show idx => GHC.Show.Show (Math.Combinat.Groups.Free.Generator idx)
instance GHC.Classes.Ord idx => GHC.Classes.Ord (Math.Combinat.Groups.Free.Generator idx)
instance GHC.Classes.Eq idx => GHC.Classes.Eq (Math.Combinat.Groups.Free.Generator idx)
instance GHC.Base.Functor Math.Combinat.Groups.Free.Generator
-- | Set partitions.
--
-- See eg. http://en.wikipedia.org/wiki/Partition_of_a_set
module Math.Combinat.Partitions.Set
-- | A partition of the set [1..n] (in standard order)
newtype SetPartition
SetPartition :: [[Int]] -> SetPartition
_standardizeSetPartition :: [[Int]] -> [[Int]]
fromSetPartition :: SetPartition -> [[Int]]
toSetPartitionUnsafe :: [[Int]] -> SetPartition
toSetPartition :: [[Int]] -> SetPartition
_isSetPartition :: [[Int]] -> Bool
-- | The "shape" of a set partition is the partition we get when we forget
-- the set structure, keeping only the cardinalities.
setPartitionShape :: SetPartition -> Partition
-- | Synonym for setPartitionsNaive
setPartitions :: Int -> [SetPartition]
-- | Synonym for setPartitionsWithKPartsNaive
--
--
-- sort (setPartitionsWithKParts k n) == sort [ p | p <- setPartitions n , numberOfParts p == k ]
--
setPartitionsWithKParts :: Int -> Int -> [SetPartition]
-- | List all set partitions of [1..n], naive algorithm
setPartitionsNaive :: Int -> [SetPartition]
-- | Set partitions of the set [1..n] into k parts
setPartitionsWithKPartsNaive :: Int -> Int -> [SetPartition]
-- | Set partitions are counted by the Bell numbers
countSetPartitions :: Int -> Integer
-- | Set partitions of size k are counted by the Stirling numbers
-- of second kind
countSetPartitionsWithKParts :: Int -> Int -> Integer
instance GHC.Read.Read Math.Combinat.Partitions.Set.SetPartition
instance GHC.Show.Show Math.Combinat.Partitions.Set.SetPartition
instance GHC.Classes.Ord Math.Combinat.Partitions.Set.SetPartition
instance GHC.Classes.Eq Math.Combinat.Partitions.Set.SetPartition
instance Math.Combinat.Classes.HasNumberOfParts Math.Combinat.Partitions.Set.SetPartition
-- | Non-crossing partitions.
--
-- See eg. http://en.wikipedia.org/wiki/Noncrossing_partition
--
-- Non-crossing partitions of the set [1..n] are encoded as
-- lists of lists in standard form: Entries decreasing in each block and
-- blocks listed in increasing order of their first entries. For example
-- the partition in the diagram
--
--
-- is represented as
--
--
-- NonCrossing [[3],[5,4,2],[7,6,1],[9,8]]
--
module Math.Combinat.Partitions.NonCrossing
-- | A non-crossing partition of the set [1..n] in standard form:
-- entries decreasing in each block and blocks listed in increasing order
-- of their first entries.
newtype NonCrossing
NonCrossing :: [[Int]] -> NonCrossing
-- | Checks whether a set partition is noncrossing.
--
-- Implementation method: we convert to a Dyck path and then back again,
-- and finally compare. Probably not very efficient, but should be better
-- than a naive check for crosses...)
_isNonCrossing :: [[Int]] -> Bool
-- | Warning: This function assumes the standard ordering!
_isNonCrossingUnsafe :: [[Int]] -> Bool
-- | Convert to standard form: entries decreasing in each block and blocks
-- listed in increasing order of their first entries.
_standardizeNonCrossing :: [[Int]] -> [[Int]]
fromNonCrossing :: NonCrossing -> [[Int]]
toNonCrossingUnsafe :: [[Int]] -> NonCrossing
-- | Throws an error if the input is not a non-crossing partition
toNonCrossing :: [[Int]] -> NonCrossing
toNonCrossingMaybe :: [[Int]] -> Maybe NonCrossing
-- | If a set partition is actually non-crossing, then we can convert it
setPartitionToNonCrossing :: SetPartition -> Maybe NonCrossing
-- | Bijection between Dyck paths and noncrossing partitions
--
-- Based on: David Callan: Sets, Lists and Noncrossing Partitions
--
-- Fails if the input is not a Dyck path.
dyckPathToNonCrossingPartition :: LatticePath -> NonCrossing
-- | Safe version of dyckPathToNonCrossingPartition
dyckPathToNonCrossingPartitionMaybe :: LatticePath -> Maybe NonCrossing
-- | The inverse bijection (should never fail proper NonCrossing-s)
nonCrossingPartitionToDyckPath :: NonCrossing -> LatticePath
-- | Safe version nonCrossingPartitionToDyckPath
_nonCrossingPartitionToDyckPathMaybe :: [[Int]] -> Maybe LatticePath
-- | Lists all non-crossing partitions of [1..n]
--
-- Equivalent to (but orders of magnitude faster than) filtering out the
-- non-crossing ones:
--
--
-- (sort $ catMaybes $ map setPartitionToNonCrossing $ setPartitions n) == sort (nonCrossingPartitions n)
--
nonCrossingPartitions :: Int -> [NonCrossing]
-- | Lists all non-crossing partitions of [1..n] into k
-- parts.
--
--
-- sort (nonCrossingPartitionsWithKParts k n) == sort [ p | p <- nonCrossingPartitions n , numberOfParts p == k ]
--
nonCrossingPartitionsWithKParts :: Int -> Int -> [NonCrossing]
-- | Non-crossing partitions are counted by the Catalan numbers
countNonCrossingPartitions :: Int -> Integer
-- | Non-crossing partitions with k parts are counted by the
-- Naranaya numbers
countNonCrossingPartitionsWithKParts :: Int -> Int -> Integer
-- | Uniformly random non-crossing partition
randomNonCrossingPartition :: RandomGen g => Int -> g -> (NonCrossing, g)
instance GHC.Read.Read Math.Combinat.Partitions.NonCrossing.NonCrossing
instance GHC.Show.Show Math.Combinat.Partitions.NonCrossing.NonCrossing
instance GHC.Classes.Ord Math.Combinat.Partitions.NonCrossing.NonCrossing
instance GHC.Classes.Eq Math.Combinat.Partitions.NonCrossing.NonCrossing
instance Math.Combinat.Classes.HasNumberOfParts Math.Combinat.Partitions.NonCrossing.NonCrossing
-- | N-ary trees.
module Math.Combinat.Trees.Nary
-- | Multi-way trees, also known as rose trees.
data Tree a :: * -> *
Node :: a -> Forest a -> Tree a
-- | label value
[rootLabel] :: Tree a -> a
-- | zero or more child trees
[subForest] :: Tree a -> Forest a
-- | Ternary trees on n nodes (synonym for regularNaryTrees
-- 3)
ternaryTrees :: Int -> [Tree ()]
-- | regularNaryTrees d n returns the list of (rooted) trees on
-- n nodes where each node has exactly d children. Note
-- that the leaves do not count in n. Naive algorithm.
regularNaryTrees :: Int -> Int -> [Tree ()]
-- | All trees on n nodes where the number of children of all
-- nodes is in element of the given set. Example:
--
--
-- autoTabulate RowMajor (Right 5) $ map asciiTreeVertical
-- $ map labelNChildrenTree_
-- $ semiRegularTrees [2,3] 2
--
-- [ length $ semiRegularTrees [2,3] n | n<-[0..] ] == [1,2,10,66,498,4066,34970,312066,2862562,26824386,...]
--
--
-- The latter sequence is A027307 in OEIS:
-- https://oeis.org/A027307
--
-- Remark: clearly, we have
--
--
-- semiRegularTrees [d] n == regularNaryTrees d n
--
semiRegularTrees :: [Int] -> Int -> [Tree ()]
-- |
-- # = \frac {1} {(2n+1} \binom {3n} {n}
--
countTernaryTrees :: Integral a => a -> Integer
-- | We have
--
--
-- length (regularNaryTrees d n) == countRegularNaryTrees d n == \frac {1} {(d-1)n+1} \binom {dn} {n}
--
countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> Integer
-- | Computes the set of equivalence classes of rooted trees (in the sense
-- that the leaves of a node are unordered) with n = length
-- ks leaves where the set of heights of the leaves matches the
-- given set of numbers. The height is defined as the number of
-- edges from the leaf to the root.
--
-- TODO: better name?
derivTrees :: [Int] -> [Tree ()]
-- | Vertical ASCII drawing of a tree, without labels. Example:
--
--
-- autoTabulate RowMajor (Right 5) $ map asciiTreeVertical_ $ regularNaryTrees 2 4
--
--
-- Nodes are denoted by @, leaves by *.
asciiTreeVertical_ :: Tree a -> ASCII
-- | Prints all labels. Example:
--
--
-- asciiTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666
--
--
-- Nodes are denoted by (label), leaves by label.
asciiTreeVertical :: Show a => Tree a -> ASCII
-- | Prints the labels for the leaves, but not for the nodes.
asciiTreeVerticalLeavesOnly :: Show a => Tree a -> ASCII
type Dot = String
-- | Generates graphviz .dot file from a tree. The first argument
-- is the name of the graph.
graphvizDotTree :: Show a => Bool -> String -> Tree a -> Dot
-- | Generates graphviz .dot file from a forest. The first
-- argument tells whether to make the individual trees clustered
-- subgraphs; the second is the name of the graph.
graphvizDotForest :: Show a => Bool -> Bool -> String -> Forest a -> Dot
-- | Left is leaf, Right is node
classifyTreeNode :: Tree a -> Either a a
isTreeLeaf :: Tree a -> Maybe a
isTreeNode :: Tree a -> Maybe a
isTreeLeaf_ :: Tree a -> Bool
isTreeNode_ :: Tree a -> Bool
treeNodeNumberOfChildren :: Tree a -> Int
countTreeNodes :: Tree a -> Int
countTreeLeaves :: Tree a -> Int
countTreeLabelsWith :: (a -> Bool) -> Tree a -> Int
countTreeNodesWith :: (Tree a -> Bool) -> Tree a -> Int
-- | The leftmost spine (the second element of the pair is the leaf node)
leftSpine :: Tree a -> ([a], a)
-- | The leftmost spine without the leaf node
leftSpine_ :: Tree a -> [a]
rightSpine :: Tree a -> ([a], a)
rightSpine_ :: Tree a -> [a]
-- | The length (number of edges) on the left spine
--
--
-- leftSpineLength tree == length (leftSpine_ tree)
--
leftSpineLength :: Tree a -> Int
rightSpineLength :: Tree a -> Int
-- | Adds unique labels to the nodes (including leaves) of a Tree.
addUniqueLabelsTree :: Tree a -> Tree (a, Int)
-- | Adds unique labels to the nodes (including leaves) of a Forest
addUniqueLabelsForest :: Forest a -> Forest (a, Int)
addUniqueLabelsTree_ :: Tree a -> Tree Int
addUniqueLabelsForest_ :: Forest a -> Forest Int
-- | Attaches the depth to each node. The depth of the root is 0.
labelDepthTree :: Tree a -> Tree (a, Int)
labelDepthForest :: Forest a -> Forest (a, Int)
labelDepthTree_ :: Tree a -> Tree Int
labelDepthForest_ :: Forest a -> Forest Int
-- | Attaches the number of children to each node.
labelNChildrenTree :: Tree a -> Tree (a, Int)
labelNChildrenForest :: Forest a -> Forest (a, Int)
labelNChildrenTree_ :: Tree a -> Tree Int
labelNChildrenForest_ :: Forest a -> Forest Int
instance Math.Combinat.Classes.HasNumberOfNodes (Data.Tree.Tree a)
instance Math.Combinat.Classes.HasNumberOfLeaves (Data.Tree.Tree a)
instance Math.Combinat.ASCII.DrawASCII (Data.Tree.Tree ())
module Math.Combinat.Trees
-- | A collection of functions to generate, manipulate, visualize and count
-- combinatorial objects like partitions, compositions, permutations,
-- braids, Young tableaux, lattice paths, various tree structures, etc
-- etc.
--
-- See also the combinat-diagrams library for generating
-- graphical representations of (some of) these structure using the
-- diagrams library
-- (http://projects.haskell.org/diagrams).
--
-- The long-term goals are
--
--
-- - generate most of the standard structures;
-- - manipulate these structures;
-- - visualize these structures;
-- - the generation should be efficient;
-- - to be able to enumerate the structures with constant memory
-- usage;
-- - to be able to randomly sample from them;
-- - finally, to be a repository of algorithms.
--
--
-- The short-term goal is simply to generate and manipulate many
-- interesting structures.
--
-- Naming conventions (subject to change):
--
--
-- - prime suffix: additional constrains, typically more general;
-- - underscore prefix: use plain lists instead of other types with
-- enforced invariants;
-- - "random" prefix: generates random objects (typically with uniform
-- distribution);
-- - "count" prefix: counting functions.
--
--
-- This module re-exports the most commonly used modules.
module Math.Combinat