-- 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.1 -- | 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 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 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 [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 Show SameSize instance Show CyclicPermutation instance Eq Nat instance Ord Nat instance Show Nat instance Num Nat instance Random Nat instance Eq Elem instance Eq DisjointCycles instance Ord DisjointCycles instance Show DisjointCycles instance Read DisjointCycles instance Eq Permutation instance Ord Permutation instance Show Permutation instance Read Permutation instance Arbitrary SameSize instance Arbitrary DisjointCycles instance Arbitrary CyclicPermutation instance Arbitrary Permutation instance Arbitrary Nat instance Random SameSize instance Random DisjointCycles instance Random CyclicPermutation instance Random 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] -- -- 
--   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 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, -- http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux. 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, -- -- 
--   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 -- | 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]] -- | 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]] -- | # = binom { n } { k }. countKSublists :: Int -> Int -> Integer -- | # = 2^n. 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 -- --
    --
  1. to be efficient;
    2. --
  2. to be able to enumerate the structures with constant memory -- usage.
    3. --
-- -- The short-term goal is to generate many interesting structures. -- -- Naming conventions (subject to change): -- -- module Math.Combinat binomial :: Int -> Int -> Integer factorial :: Int -> Integer