-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generation of various combinatorial objects.
--
@package combinat
@version 0.2.6.2
-- | 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])
-- | 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)
-- | Partitions of integers and multisets. Integer partitions are
-- nonincreasing sequences of positive integers.
--
-- See:
--
--
module Math.Combinat.Partitions
-- | A partition of an integer. The additional invariant enforced here is
-- that partitions are monotone decreasing sequences of positive
-- integers.
data Partition
-- | Checks whether the input is an integer partition. See the note at
-- isPartition!
toPartition :: [Int] -> Partition
-- | Assumes that the input is decreasing.
toPartitionUnsafe :: [Int] -> Partition
-- | Sorts the input, and cuts the nonpositive elements.
mkPartition :: [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
class HasNumberOfParts p
numberOfParts :: HasNumberOfParts p => p -> Int
-- | Partitions of d, fitting into a given rectangle. The order is again
-- lexicographic.
partitions' :: (Int, Int) -> Int -> [Partition]
-- | Integer partitions of d, fitting into a given rectangle, as
-- lists.
_partitions' :: (Int, Int) -> Int -> [[Int]]
countPartitions' :: (Int, Int) -> Int -> Integer
-- | Partitions of d.
partitions :: Int -> [Partition]
-- | Partitions of d, as lists
_partitions :: Int -> [[Int]]
countPartitions :: 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]
-- | 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
countPartitionsWithKParts :: Int -> Int -> Integer
printFerrerDiagram :: Partition -> IO ()
-- | Synonym for ferrerDiagramEnglishNotation
ferrerDiagram :: Partition -> String
ferrerDiagramEnglishNotation :: Partition -> String
ferrerDiagramFrenchNotation :: Partition -> String
ferrerDiagramEnglishNotation' :: Char -> Partition -> String
ferrerDiagramFrenchNotation' :: Char -> Partition -> String
-- | Partitions of a multiset.
partitionMultiset :: (Eq a, Ord a) => [a] -> [[[a]]]
-- | 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]]
instance Eq Partition
instance Ord Partition
instance Show Partition
instance Read Partition
instance HasNumberOfParts Partition
-- | 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
-- | 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 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
-- | 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.
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
-- | 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)
forgetNodeDecorations :: BinTree' a b -> BinTree a
data Paren
LeftParen :: Paren
RightParen :: Paren
parenthesesToString :: [Paren] -> String
stringToParentheses :: String -> [Paren]
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]
-- | 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:
--
--
-- mapM_ printBinaryTree_ $ binaryTrees 4
--
printBinaryTree_ :: BinTree a -> IO ()
drawBinaryTree_ :: BinTree a -> String
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 (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 Paren
instance Ord Paren
instance Show Paren
instance Read Paren
instance Traversable BinTree
instance Foldable BinTree
instance Functor BinTree
-- | Dyck paths, lattice paths, etc
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]
-- | 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)]
-- | 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]
-- | 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]
-- | 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
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:
--
--
-- mapM_ printTreeVertical
-- $ map labelNChildrenTree_
-- $ semiRegularTrees [2,3] n
--
-- [ 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:
--
--
-- mapM_ printTreeVertical_ $ regularNaryTrees 2 3
--
printTreeVertical_ :: Tree a -> IO ()
-- | Prints all labels.
--
-- Example:
--
--
-- printTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666
--
printTreeVertical :: Show a => Tree a -> IO ()
-- | Prints the labels for the leaves, but not for the nonempty nodes
printTreeVerticalLeavesOnly :: Show a => Tree a -> IO ()
-- | Nodes are denoted by @, leaves by *.
drawTreeVertical_ :: Tree a -> String
-- | Nodes are denoted by (label), leaves by label.
drawTreeVertical :: Show a => Tree a -> String
-- | Nodes are denoted by @, leaves by label.
drawTreeVerticalLeavesOnly :: Show a => Tree a -> String
-- | 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
-- | Creates graphviz .dot files from various structures, for
-- example trees.
module Math.Combinat.Graphviz
type Dot = String
binTreeDot :: Show a => String -> BinTree a -> Dot
binTree'Dot :: (Show a, Show b) => String -> BinTree' a b -> Dot
-- | Generates graphviz .dot file from a tree. The first argument
-- is the name of the graph.
treeDot :: 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.
forestDot :: Show a => Bool -> Bool -> String -> Forest a -> Dot
-- | 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.
--
-- 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