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


-- | Trees, forests, etc. See: Donald E. Knuth: The Art of Computer
--   Programming, vol 4, pre-fascicle 4A.
module Math.Combinat.Trees

-- | A binary tree with leaves decorated with type <tt>a</tt>.
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
--   <tt>a</tt> and <tt>b</tt>, 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 <a>fasc4A_algorithm_P</a>.
nestedParentheses :: Int -> [[Paren]]

-- | Synonym for <a>fasc4A_algorithm_W</a>.
randomNestedParentheses :: (RandomGen g) => Int -> g -> ([Paren], g)

-- | Synonym for <a>fasc4A_algorithm_U</a>.
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 <a>fasc4A_algorithm_P</a>. 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 <a>binaryTreesNaive</a>.
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
--   <a>fasc4A_algorithm_R</a>.
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 <tt>[0..2n]</tt>). 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 Functor BinTree


-- | 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 <tt>[1..n]</tt>.
data Permutation
fromPermutation :: Permutation -> [Int]

-- | Assumes that the input is a permutation of the numbers
--   <tt>[1..n]</tt>.
toPermutationUnsafe :: [Int] -> Permutation

-- | Checks whether the input is a permutation of the numbers
--   <tt>[1..n]</tt>.
isPermutation :: [Int] -> Bool

-- | Checks the input.
toPermutation :: [Int] -> Permutation

-- | Returns <tt>n</tt>, where the input is a permutation of the numbers
--   <tt>[1..n]</tt>
permutationSize :: Permutation -> Int

-- | Action of a permutation on a set. If our permutation is encoded with
--   the sequence <tt>[p1,p2,...,pn]</tt>, then in the two-line notation we
--   have
--   
--   <pre>
--   ( 1  2  3  ... n  )
--   ( p1 p2 p3 ... pn )
--   </pre>
--   
--   We adopt the convention that permutations act <i>on the left</i> (as
--   opposed to Knuth, where they act on the right). Thus,
--   
--   <pre>
--   permute pi1 (permute pi2 set) == permute (pi1 `multiply` pi2) set
--   </pre>
--   
--   The second argument should be an array with bounds <tt>(1,n)</tt>. The
--   function checks the array bounds.
permute :: Permutation -> Array Int a -> Array Int a

-- | The list should be of length <tt>n</tt>.
permuteList :: Permutation -> [a] -> [a]

-- | Multiplies two permutations together. See <a>permute</a> for our
--   conventions.
multiply :: Permutation -> Permutation -> Permutation

-- | The inverse permutation
inverse :: Permutation -> Permutation

-- | A synonym for <a>permutationsNaive</a>
permutations :: Int -> [Permutation]
_permutations :: Int -> [[Int]]

-- | Permutations of <tt>[1..n]</tt> in lexicographic order, naive
--   algorithm.
permutationsNaive :: Int -> [Permutation]
_permutationsNaive :: Int -> [[Int]]

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

-- | A synonym for <a>randomPermutationDurstenfeld</a>.
randomPermutation :: (RandomGen g) => Int -> g -> (Permutation, g)
_randomPermutation :: (RandomGen g) => Int -> g -> ([Int], g)

-- | A synonym for <a>randomCyclicPermutationSattolo</a>.
randomCyclicPermutation :: (RandomGen g) => Int -> g -> (Permutation, g)
_randomCyclicPermutation :: (RandomGen g) => Int -> g -> ([Int], g)

-- | Generates a uniformly random permutation of <tt>[1..n]</tt>.
--   Durstenfeld's algorithm (see
--   <a>http://en.wikipedia.org/wiki/Knuth_shuffle</a>).
randomPermutationDurstenfeld :: (RandomGen g) => Int -> g -> (Permutation, g)

-- | Generates a uniformly random <i>cyclic</i> permutation of
--   <tt>[1..n]</tt>. Sattolo's algorithm (see
--   <a>http://en.wikipedia.org/wiki/Knuth_shuffle</a>).
randomCyclicPermutationSattolo :: (RandomGen g) => Int -> g -> (Permutation, g)

-- | Generates all permutations of a multiset. The order is lexicographic.
--   A synonym for <a>fasc2B_algorithm_L</a>
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


-- | 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]]


-- | Subsets.
module Math.Combinat.Sets

-- | Sublists of a list having given number of elements.
kSublists :: Int -> [a] -> [[a]]

-- | All sublists of a list.
sublists :: [a] -> [[a]]

-- | <tt># = binom { n } { k }</tt>.
countKSublists :: Int -> Int -> Integer

-- | <tt># = 2^n</tt>.
countSublists :: Int -> Integer


-- | 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>"random" prefix: generates random objects (typically with uniform
--   distribution);</li>
--   <li>"count" prefix: counting functions.</li>
--   </ul>
module Math.Combinat