-- 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.1


-- | Trees, forests, etc. See: Donald E. Knuth: The Art of Computer
--   Programming, vol 4, pre-fascicle 4A.
module Math.Combinat.Trees
data BinTree a
Branch :: (BinTree a) -> (BinTree a) -> BinTree a
Leaf :: a -> BinTree a
leaf :: BinTree ()
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 <a>fasc4A_algorithm_P</a>.
nestedParentheses :: Int -> [[Paren]]

-- | 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 all binary trees with n nodes.
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 ()]
instance Eq Paren
instance Ord Paren
instance Show Paren
instance Read Paren
instance (Eq a) => Eq (BinTree a)
instance (Ord a) => Ord (BinTree a)
instance (Show a) => Show (BinTree a)
instance (Read a) => Read (BinTree a)


-- | Permutations. See: Donald E. Knuth: The Art of Computer Programming,
--   vol 4, pre-fascicle 2B.
module Math.Combinat.Permutations

-- | Permutations of [1..n] in lexicographic order, naive algorithm.
_permutations :: Int -> [[Int]]

-- | # = n!
countPermutations :: Int -> Integer

-- | Generates all permutations of a multiset. The order is lexicographic.
permute :: (Eq a, Ord a) => [a] -> [[a]]

-- | # = \frac { (sum_i n_i) ! } { \prod_i (n_i !) }
countPermute :: (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]]


-- | Partitions. Partitions are nonincreasing sequences of positive
--   integers.
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.
toPartition :: [Int] -> Partition

-- | Assumes that the input is decreasing.
toPartitionUnsafe :: [Int] -> Partition

-- | Sorts the input.
mkPartition :: [Int] -> Partition
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
_dualPartition :: [Int] -> [Int]

-- | The dual (or conjugate) partition.
dualPartition :: Partition -> Partition

-- | 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 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
instance Eq Partition
instance Ord Partition
instance Show Partition
instance Read Partition


-- | 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]
--   
--   <pre>
--   1  3  4  6  7
--   2  5  8 10
--   9
--   </pre>
--   
--   is encoded conveniently as
--   
--   <pre>
--   [ [ 1 , 3 , 4 , 6 , 7 ]
--   , [ 2 , 5 , 8 ,10 ]
--   , [ 9 ]
--   ]
--   </pre>
module Math.Combinat.Tableaux
type Tableau a = [[a]]
_shape :: Tableau a -> [Int]
shape :: Tableau a -> Partition
dualTableau :: Tableau a -> Tableau a
hooks :: 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,
--   <a>http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux</a>.
standardYoungTableaux :: Partition -> [Tableau Int]

-- | hook-length formula
countStandardYoungTableaux :: Partition -> Integer


-- | Combinations
module Math.Combinat.Combinations

-- | Combinations fitting into a given shape and having a given degree. The
--   order is lexicographic, that is,
--   
--   <pre>
--   sort cs == cs where cs = combinations' shape k
--   </pre>
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


-- | Tuples.
module Math.Combinat.Tuples

-- | "Tuples" fitting into a give shape. The order is lexicographic, that
--   is,
--   
--   <pre>
--   sort ts == ts where ts = tuples' shape
--   </pre>
--   
--   Example:
--   
--   <pre>
--   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]]
--   </pre>
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 collection of functions to generate combinatorial objects like
--   partitions, combinations, permutations, Young tableaux, various trees,
--   etc.
--   
--   The long-term goals are
--   
--   <ol>
--   <li>to be efficient;</li>
--   <li>to be able to enumerate the structures with constant memory
--   usage.</li>
--   </ol>
--   
--   The short-term goal is to generate many interesting structures.
--   
--   Naming conventions (subject to change):
--   
--   <ul>
--   <li>prime suffix: additional constrains, typically more general;</li>
--   <li>underscore prefix: use plain lists instead of other types with
--   enforced invariants;</li>
--   <li>"count" prefix: counting functions.</li>
--   </ul>
module Math.Combinat