-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generation of various combinatorial objects.
--
-- A collection of functions to generate combinatorial objects like
-- partitions, combinations, permutations, Young tableaux, various trees,
-- etc.
@package combinat
@version 0.2.4
-- | 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
-- | 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",
-- http://www.research.att.com/~njas/sequences/ .
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
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.
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.
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
-- | 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]]
-- | All possible ways to choose k elements from a list, with
-- repetitions. "Symmetric power" for lists. See also
-- Math.Combinat.Combinations. TODO: better name?
combine :: 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
-- | Combinations
module Math.Combinat.Combinations
-- | Combinations fitting into a given shape and having a given degree. The
-- order is lexicographic, that is,
--
--
-- sort cs == cs where cs = combinations' shape k
--
combinations' :: [Int] -> Int -> [[Int]]
countCombinations' :: [Int] -> Int -> Integer
-- | All combinations fitting into a given shape.
allCombinations' :: [Int] -> [[[Int]]]
-- | Combinations of a given length.
combinations :: Int -> Int -> [[Int]]
-- | # = \binom { len+d-1 } { len-1 }
countCombinations :: Int -> Int -> Integer
-- | Positive combinations of a given length.
combinations1 :: Int -> Int -> [[Int]]
countCombinations1 :: Int -> Int -> Integer
-- | Partitions. Partitions are nonincreasing sequences of positive
-- integers.
--
-- See also Donald E. Knuth: The Art of Computer Programming, vol 4,
-- pre-fascicle 3B.
module Math.Combinat.Partitions
-- | The additional invariant enforced here is that partitions are monotone
-- decreasing sequences of positive integers.
data Partition
-- | Checks whether the input is a 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,2,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 partition.
countAutomorphisms :: Partition -> Integer
_countAutomorphisms :: [Int] -> Integer
-- | Partitions of d, fitting into a given rectangle. The order is again
-- lexicographic.
partitions' :: (Int, Int) -> Int -> [Partition]
-- | 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
-- | All partitions fitting into a given rectangle.
allPartitions' :: (Int, Int) -> [[Partition]]
-- | All partitions up to a given degree.
allPartitions :: Int -> [[Partition]]
-- | # = \binom { h+w } { h }
countAllPartitions' :: (Int, Int) -> Integer
countAllPartitions :: Int -> Integer
-- | 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
-- | N-ary trees.
module Math.Combinat.Trees.Nary
-- | Computes the set of equivalence classes of 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 ()]
-- | Adds unique labels to a Tree.
addUniqueLabelsTree :: Tree a -> Tree (a, Int)
-- | Adds unique labels to 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
-- | 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
-- | 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
-- | 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 DisjointCycles
instance Ord DisjointCycles
instance Show DisjointCycles
instance Read DisjointCycles
instance Eq Permutation
instance Ord Permutation
instance Show Permutation
instance Read Permutation
-- | 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",
-- http://www.research.att.com/~njas/sequences/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 Hole
instance Ord Hole
instance Show Hole
instance Eq Tri
instance Ord Tri
instance Show Tri
instance Ix Tri
-- | 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
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]
-- | 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
-- lexigraphic (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)
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
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 => 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 -> String -> Forest a -> Dot
-- | A collection of functions to generate combinatorial objects like
-- partitions, combinations, permutations, Young tableaux, various trees,
-- etc.
--
-- The long-term goals are
--
--
-- - to be efficient;
-- - to be able to enumerate the structures with constant memory
-- usage.
--
--
-- The short-term goal is 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.
--
module Math.Combinat