-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generation of various combinatorial objects.
--
@package combinat
@version 0.2.7.0
-- | 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
-- | 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]]]
-- | 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
-- | Some basic 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]
-- | Convolution of series. The result is always an infinite list. Warning:
-- This is slow!
convolve :: Num a => [a] -> [a] -> [a]
-- | Convolution of many series. Still slow!
convolveMany :: Num a => [[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]
data Sign
Plus :: Sign
Minus :: Sign
signValue :: Num a => Sign -> 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]
instance Eq Sign
instance Show Sign
-- | 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]
-- | 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])
-- | 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]
-- | 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
-- | Extends an ASCII figure with spaces horizontally to the given width
hExtendTo :: HAlign -> Int -> ASCII -> ASCII
-- | Extends an ASCII figure with spaces vertically to the given height
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
-- | 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]
-- | 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
-- | Horizontal concatenation
hCatWith :: VAlign -> HSep -> [ASCII] -> ASCII
-- | Vertical concatenation
vCatWith :: HAlign -> VSep -> [ASCII] -> ASCII
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 box of the given size
asciiBox :: (Int, Int) -> ASCII
-- | An "rounded" ASCII box of the given size
roundedAsciiBox :: (Int, Int) -> ASCII
asciiNumber :: Int -> ASCII
asciiShow :: Show a => a -> ASCII
instance Eq HAlign
instance Show HAlign
instance Eq VAlign
instance Show VAlign
instance Show HSep
instance Show VSep
instance Eq MatrixOrder
instance Ord MatrixOrder
instance Show MatrixOrder
instance Read MatrixOrder
instance Show 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]]
-- | A few important number sequences.
--
-- See the "On-Line Encyclopedia of Integer Sequences",
-- https://oeis.org .
module Math.Combinat.Numbers
-- |
-- (-1)^k
--
paritySign :: Integral a => a -> Integer
-- | A000142.
factorial :: Integral a => a -> Integer
-- | A006882.
doubleFactorial :: Integral a => a -> Integer
-- | A007318.
binomial :: Integral a => a -> a -> 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
-- | All possible ways to choose k elements from a list, without
-- repetitions. "Antisymmetric power" for lists. Synonym for
-- kSublists.
choose :: Int -> [a] -> [[a]]
-- | 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, 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.
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: Donald E. Knuth: The Art of Computer Programming,
-- vol 4, pre-fascicle 2B.
module Math.Combinat.Permutations
-- | Standard notation for permutations. Internally it is an array of the
-- integers [1..n].
data Permutation
-- | Disjoint cycle notation for permutations. Internally it is
-- [[Int]].
data DisjointCycles
fromPermutation :: Permutation -> [Int]
permutationArray :: Permutation -> Array Int Int
-- | Assumes that the input is a permutation of the numbers
-- [1..n].
toPermutationUnsafe :: [Int] -> Permutation
arrayToPermutationUnsafe :: Array Int Int -> Permutation
-- | Checks whether the input is a permutation of the numbers
-- [1..n].
isPermutation :: [Int] -> Bool
-- | Checks the input.
toPermutation :: [Int] -> Permutation
-- | Returns n, where the input is a permutation of the numbers
-- [1..n]
permutationSize :: Permutation -> Int
fromDisjointCycles :: DisjointCycles -> [[Int]]
disjointCyclesUnsafe :: [[Int]] -> DisjointCycles
-- | This is compatible with Maple's convert(perm,'disjcyc').
permutationToDisjointCycles :: Permutation -> DisjointCycles
disjointCyclesToPermutation :: Int -> DisjointCycles -> Permutation
isEvenPermutation :: Permutation -> Bool
isOddPermutation :: Permutation -> Bool
-- | Plus 1 or minus 1.
signOfPermutation :: Num a => Permutation -> a
isCyclicPermutation :: Permutation -> Bool
-- | 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 left (as
-- opposed to Knuth, where they act on the right). Thus,
--
--
-- permute pi1 (permute pi2 set) == permute (pi1 `multiply` pi2) set
--
--
-- The second argument should be an array with bounds (1,n). The
-- function checks the array bounds.
permute :: Permutation -> Array Int a -> Array Int a
-- | The list should be of length n.
permuteList :: Permutation -> [a] -> [a]
-- | Multiplies two permutations together. See permute for our
-- conventions.
multiply :: Permutation -> Permutation -> Permutation
-- | The inverse permutation.
inverse :: Permutation -> Permutation
-- | The trivial permutation.
identity :: Int -> Permutation
-- | A synonym for permutationsNaive
permutations :: Int -> [Permutation]
_permutations :: Int -> [[Int]]
-- | 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 Eq Permutation
instance Ord Permutation
instance Show Permutation
instance Read Permutation
instance Eq DisjointCycles
instance Ord DisjointCycles
instance Show DisjointCycles
instance Read DisjointCycles
-- | 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
class HasNumberOfParts p
numberOfParts :: HasNumberOfParts p => p -> Int
-- | 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
-- | Note: we only check that the sequence is ordered, but we do not
-- check for negative elements. This can be useful when working with
-- symmetric functions. It may also change in the future...
isPartition :: [Int] -> Bool
fromPartition :: Partition -> [Int]
-- | The first element of the sequence.
height :: Partition -> Int
-- | The length of the sequence.
width :: Partition -> Int
heightWidth :: Partition -> (Int, Int)
-- | The weight of the partition (that is, the sum of the corresponding
-- sequence).
weight :: Partition -> Int
-- | The dual (or conjugate) partition.
dualPartition :: Partition -> Partition
_dualPartition :: [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)]
-- | Computes the number of "automorphisms" of a given integer partition.
countAutomorphisms :: Partition -> Integer
_countAutomorphisms :: [Int] -> Integer
-- | 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
-- | 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
-- | Partitions of d, as lists
_partitions :: Int -> [[Int]]
-- | Partitions of d.
partitions :: Int -> [Partition]
countPartitions :: Int -> Integer
-- | All integer partitions fitting into a given rectangle.
allPartitions' :: (Int, Int) -> [[Partition]]
-- | All integer partitions up to a given degree (that is, all integer
-- partitions whose sum is less or equal to d)
allPartitions :: Int -> [[Partition]]
-- | # = \binom { h+w } { h }
countAllPartitions' :: (Int, Int) -> Integer
countAllPartitions :: Int -> Integer
-- | 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
-- | Returns True of the first partition is a subpartition (that
-- is, fit inside) of the second. This includes equality
isSubPartitionOf :: 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]]
-- | 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 Eq Partition
instance Ord Partition
instance Show Partition
instance Read Partition
instance Eq PartitionConvention
instance Show PartitionConvention
instance HasNumberOfParts 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
type Tableau a = [[a]]
_shape :: Tableau a -> [Int]
shape :: Tableau a -> Partition
dualTableau :: Tableau a -> Tableau a
content :: 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
rowWord :: Tableau a -> [a]
rowWordToTableau :: Ord a => [a] -> Tableau a
columnWord :: Tableau a -> [a]
columnWordToTableau :: Ord a => [a] -> Tableau a
-- | 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
-- | 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
-- | 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 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 "Kostka 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.Kostka
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
-- | Generates all tableaux of size k. Effective for
-- k<=6.
kostkaTableaux :: Int -> [TriangularArray Int]
_kostkaTableaux :: Int -> [Tableau Int]
countKostkaTableaux :: Int -> [Int]
kostkaContent :: TriangularArray Int -> Int
_kostkaContent :: Tableau Int -> Int
instance Eq Tri
instance Ord Tri
instance Show Tri
instance Eq Hole
instance Ord Hole
instance Show Hole
instance Ix Tri
-- | 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 Eq PlanePart
instance Ord PlanePart
instance Show PlanePart
-- | 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
-- | 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 Eq SetPartition
instance Ord SetPartition
instance Show SetPartition
instance Read SetPartition
instance HasNumberOfParts SetPartition
-- | 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 ()
-- | 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]
-- | 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)
-- | 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 Eq Paren
instance Ord Paren
instance Show Paren
instance Read Paren
instance (Eq a, Eq b) => Eq (BinTree' a b)
instance (Ord a, Ord b) => Ord (BinTree' a b)
instance (Show a, Show b) => Show (BinTree' a b)
instance (Read a, Read b) => Read (BinTree' a b)
instance Eq a => Eq (BinTree a)
instance Ord a => Ord (BinTree a)
instance Show a => Show (BinTree a)
instance Read a => Read (BinTree a)
instance Traversable BinTree
instance Foldable BinTree
instance Functor 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 Eq Step
instance Ord Step
instance Show Step
-- | 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 Eq NonCrossing
instance Ord NonCrossing
instance Show NonCrossing
instance Read NonCrossing
instance HasNumberOfParts NonCrossing
-- | N-ary trees.
module Math.Combinat.Trees.Nary
-- | 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
module Math.Combinat.Trees
-- | Words in free groups (and free powers of cyclic groups). This module
-- is not re-exported by Math.Combinat
module Math.Combinat.FreeGroups
-- | A generator of a (free) group
data Generator a
Gen :: a -> Generator a
Inv :: a -> Generator a
-- | The index of a generator
unGen :: Generator a -> a
-- | A word, describing (non-uniquely) an element of a group. The
-- identity element is represented (among others) by the empty word.
type Word a = [Generator a]
-- | 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 a => Word a -> Word a -> Word a
-- | 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 a => Word a -> Word a
-- | 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 a => Word a -> Word a -> Word a
-- | Multiplication in free products of Z3's
multiplyZ3 :: Eq a => Word a -> Word a -> Word a
-- | Multiplication in free products of Zm's
multiplyZm :: Eq a => Int -> Word a -> Word a -> Word a
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^2=1 (that is, free products of Z2's)
reduceWordZ2 :: Eq a => Word a -> Word a
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^3=1 (that is, free products of Z3's)
reduceWordZ3 :: Eq a => Word a -> Word a
-- | Reduces a word, where each generator x satisfies the
-- additional relation x^m=1 (that is, free products of Zm's)
reduceWordZm :: Eq a => Int -> Word a -> Word a
-- | 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 Eq a => Eq (Generator a)
instance Ord a => Ord (Generator a)
instance Show a => Show (Generator a)
instance Read a => Read (Generator a)
instance Functor Generator
-- | A collection of functions to generate combinatorial objects like
-- partitions, compositions, permutations, Young tableaux, various trees,
-- etc etc.
--
-- See also the combinat-diagrams library for generating
-- graphical representations of these structure using the
-- diagrams library
-- (http://projects.haskell.org/diagrams).
--
-- The long-term goals are
--
--
-- - generate most of the standard structures;
-- - while being efficient;
-- - to be able to enumerate the structures with constant memory
-- usage;
-- - and to be able to randomly sample from them.
-- - finally, be a repository of algorithms
--
--
-- The short-term goal is simply to generate 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 common modules.
module Math.Combinat