-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Count, enumerate, rank and unrank combinatorial objects
--   
--   Counting, enumerating, ranking and unranking of combinatorial objects.
--   Well-known and less well-known basic combinatoric problems and
--   examples.
--   
--   The functions are not implemented in obviously stupid ways, but they
--   are also not optimized to the maximum extent. The package is plain
--   Haskell 98.
--   
--   See also:
--   
--   <ul>
--   <li><tt>exact-combinatorics</tt>: Efficient computations of large
--   combinatoric numbers.</li>
--   <li><tt>combinat</tt>: Library for a similar purpose with a different
--   structure and selection of problems.</li>
--   </ul>
@package combinatorial
@version 0.1


-- | Simulation of a game with the following rules:
--   
--   Players A and B alternatingly take numbers from a set of 2*n numbers.
--   Player A can choose freely from the remaining numbers, whereas player
--   B always chooses the maximum remaining number. How many possibly
--   outcomes of the games exist? The order in which the numbers are taken
--   is not respected.
--   
--   E-Mail by Daniel Beer from 2011-10-24.
module Combinatorics.MaxNim
numberOfPossibilities :: [Int]

module Combinatorics.TreeDepth
treeDepth :: [Rational]
treeDepthSeq :: [[Integer]]

-- | <tt>nodeDepth !! n !! k</tt> is the absolute frequency of nodes with
--   depth k in trees with n nodes.
nodeDepth :: [[Integer]]

-- | <tt>nodeDegree !! n !! k</tt> is the number of nodes with outdegree k
--   in a n-node tree.
nodeDegreeProb :: [[Rational]]

-- | expected value of node degree
nodeDegreeExpect :: [Rational]

module Combinatorics.Partitions

-- | This is a very efficient implementation of <a>prodLinearFactors</a>.
pentagonalPowerSeries :: [Integer]
numPartitions :: [Integer]

-- | Give all partitions of the natural number n with summands which are at
--   least k. Not quite correct for k&gt;n.
partitionsInc :: (Integral a) => a -> a -> [[a]]
partitionsDec :: (Integral a) => a -> a -> [[a]]

-- | it shall be k&gt;0 &amp;&amp; n&gt;=0 ==&gt; partitionsInc k n ==
--   allPartitionsInc !! k !! n type Int is needed because of list node
--   indexing
allPartitionsInc :: [[[[Int]]]]
propInfProdLinearFactors :: Int -> Bool
propPentagonalPowerSeries :: Int -> Bool
propPentagonalsDifP :: Int -> Bool
propPentagonalsDifN :: Int -> Bool
propPartitions :: Int -> Int -> Bool
propNumPartitions :: Int -> Bool


-- | How many possibilities are there for representing an amount of n ct by
--   the Euro coins 1ct, 2ct, 5ct, 10ct, 20ct, 50ct, 100ct, 200ct?
module Combinatorics.Coin
values :: [Int]
representationNumbersSingle :: Int -> [Integer]
representationNumbers :: [Integer]


-- | Count and create combinatorial objects. Also see <tt>combinat</tt>
--   package.
module Combinatorics

-- | Generate list of all permutations of the input list. The list is
--   sorted lexicographically.
permute :: [a] -> [[a]]

-- | Generate list of all permutations of the input list. It is not
--   lexicographically sorted. It is slightly faster and consumes less
--   memory than the lexicographical ordering <a>permute</a>.
permuteFast :: [a] -> [[a]]

-- | All permutations share as much suffixes as possible. The reversed
--   permutations are sorted lexicographically.
permuteShare :: [a] -> [[a]]
permuteRep :: [(a, Int)] -> [[a]]
choose :: Int -> Int -> [[Bool]]

-- | Generate all choices of n elements out of the list x with repetitions.
--   "variation" seems to be used historically, but I like it more than
--   "k-permutation".
variateRep :: Int -> [a] -> [[a]]

-- | Generate all choices of n elements out of the list x without
--   repetitions. It holds <tt> variate (length xs) xs == permute xs </tt>
variate :: Int -> [a] -> [[a]]

-- | Generate all choices of n elements out of the list x respecting the
--   order in x and without repetitions.
tuples :: Int -> [a] -> [[a]]
partitions :: [a] -> [([a], [a])]

-- | Number of possibilities arising in rectification of a predicate in
--   deductive database theory. Stefan Brass, "Logische Programmierung und
--   deduktive Datenbanken", 2007, page 7-60 This is isomorphic to the
--   partition of <tt>n</tt>-element sets into <tt>k</tt> non-empty
--   subsets. <a>http://oeis.org/A048993</a>
--   
--   <pre>
--   *Combinatorics&gt; map (length . uncurry rectifications) $ do x&lt;-[0..10]; y&lt;-[0..x]; return (x,[1..y::Int])
--   [1,0,1,0,1,1,0,1,3,1,0,1,7,6,1,0,1,15,25,10,1,0,1,31,90,65,15,1,0,1,63,301,350,140,21,1,0,1,127,966,1701,1050,266,28,1,0,1,255,3025,7770,6951,2646,462,36,1,0,1,511,9330,34105,42525,22827,5880,750,45,1]
--   </pre>
rectifications :: Int -> [a] -> [[a]]

-- | Their number is <tt>k^n</tt>.
setPartitions :: Int -> [a] -> [[[a]]]

-- | <pre>
--   chooseUnrank n k i == choose n k !! i
--   </pre>
chooseUnrank :: Integral a => a -> a -> a -> [Bool]
chooseUnrankMaybe :: Int -> Int -> Int -> Maybe [Bool]

-- | <a>https://en.wikipedia.org/wiki/Combinatorial_number_system</a>
chooseRank :: Integral a => [Bool] -> (a, a, a)
factorial :: Integral a => a -> a

-- | Pascal's triangle containing the binomial coefficients.
binomial :: Integral a => a -> a -> a
binomialSeq :: Integral a => a -> [a]
binomialGen :: (Integral a, Fractional b) => b -> a -> b
binomialSeqGen :: (Fractional b) => b -> [b]
multinomial :: Integral a => [a] -> a
factorials :: Num a => [a]

-- | Pascal's triangle containing the binomial coefficients. Only efficient
--   if a prefix of all rows is required. It is not efficient for picking
--   particular rows or even particular elements.
binomials :: Num a => [[a]]

-- | <tt>catalanNumber n</tt> computes the number of binary trees with
--   <tt>n</tt> nodes.
catalanNumber :: Integer -> Integer

-- | Compute the sequence of Catalan numbers by recurrence identity. It is
--   <tt>catalanNumbers !! n == catalanNumber n</tt>
catalanNumbers :: Num a => [a]
derangementNumber :: Integer -> Integer

-- | Number of fix-point-free permutations with <tt>n</tt> elements.
--   
--   <a>http://oeis.org/A000166</a>
derangementNumbers :: Num a => [a]

-- | Number of partitions of an <tt>n</tt> element set into <tt>k</tt>
--   non-empty subsets. Known as Stirling numbers
--   <a>http://oeis.org/A048993</a>.
setPartitionNumbers :: Num a => [[a]]

-- | <tt>surjectiveMappingNumber n k</tt> computes the number of surjective
--   mappings from a <tt>n</tt> element set to a <tt>k</tt> element set.
--   
--   <a>http://oeis.org/A019538</a>
surjectiveMappingNumber :: Integer -> Integer -> Integer
surjectiveMappingNumbers :: Num a => [[a]]
fibonacciNumber :: Integer -> Integer

-- | Number of possibilities to compose a 2 x n rectangle of n bricks.
--   
--   <pre>
--   |||   |--   --|
--   |||   |--   --|
--   </pre>
fibonacciNumbers :: [Integer]

module Combinatorics.Permutation.WithoutSomeFixpoints

-- | <tt>enumerate n xs</tt> list all permutations of <tt>xs</tt> where the
--   first <tt>n</tt> elements do not keep their position (i.e. are no
--   fixpoints).
--   
--   This is a generalization of derangement.
--   
--   Naive but comprehensible implementation.
enumerate :: (Eq a) => Int -> [a] -> [[a]]

-- | <a>http://oeis.org/A047920</a>
numbers :: (Num a) => [[a]]


-- | Number of possible games as described in
--   <a>http://projecteuler.net/problem=306</a>.
module Combinatorics.PaperStripGame
numbersOfGames :: [Int]
numbersOfGamesSeries :: [Integer]
treeOfGames :: Int -> Tree [Int]

module Combinatorics.Mastermind

-- | Cf. <tt>board-games</tt> package.
data Eval
Eval :: Int -> Eval
[black, white] :: Eval -> Int

-- | Given the code and a guess, compute the evaluation.
evaluate :: (Ord a) => [a] -> [a] -> Eval
evaluateAll :: (Ord a) => [[a]] -> [a] -> Map Eval Int
formatEvalHistogram :: Map Eval Int -> String

-- | <tt>numberDistinct n k b w</tt> computes the number of matching codes,
--   given that all codes have distinct symbols. <tt>n</tt> is the alphabet
--   size, <tt>k</tt> the width of the code, <tt>b</tt> the number of black
--   evaluation sticks and <tt>w</tt> the number of white evaluation
--   sticks.
numberDistinct :: Int -> Int -> Int -> Int -> Integer
instance GHC.Show.Show Combinatorics.Mastermind.Eval
instance GHC.Classes.Ord Combinatorics.Mastermind.Eval
instance GHC.Classes.Eq Combinatorics.Mastermind.Eval

module Combinatorics.CardPairs
data Card
Other :: Card
Queen :: Card
King :: Card
data CardCount i
CardCount :: i -> CardCount i
[otherCount, queenCount, kingCount] :: CardCount i -> i
charFromCard :: Card -> Char
allPossibilities :: CardSet a -> [[a]]
numberOfAllPossibilities :: CardCount Int -> Integer
possibilitiesCardsNaive :: CardCount Int -> Integer
possibilitiesCardsDynamic :: CardCount Int -> Array (CardCount Int) Integer

-- | Count the number of card set orderings with adjacent queen and king.
--   We return a triple where the elements count with respect to an
--   additional condition: (card set starts with an ordinary card ' ',
--   start with queen <tt>q</tt>, start with king <tt>k</tt>)
possibilitiesCardsBorderNaive :: CardCount Int -> CardCount Integer
possibilitiesCardsBorderDynamic :: CardCount Int -> Array (CardCount Int) (CardCount Integer)
possibilitiesCardsBorder2Dynamic :: CardCount Int -> Array (CardCount Int) (CardCount Integer)
cardSetSizeSkat :: CardCount Int
numberOfPossibilitiesSkat :: Integer
probabilitySkat :: Double
cardSetSizeRummy :: CardCount Int
numberOfPossibilitiesRummy :: Integer
probabilityRummy :: Double

-- | Allow both Jack and King adjacent to Queen.
cardSetSizeRummyJK :: CardCount Int
numberOfPossibilitiesRummyJK :: Integer
probabilityRummyJK :: Double
testCardsBorderDynamic :: (CardCount Integer, CardCount Integer, CardCount Integer)
exampleOutput :: IO ()
adjacentCouplesSmall :: [[Card]]
allPossibilitiesSmall :: [[Card]]
allPossibilitiesMedium :: [[Card]]
allPossibilitiesSkat :: [[Card]]
instance GHC.Show.Show i => GHC.Show.Show (Combinatorics.CardPairs.CardCount i)
instance GHC.Arr.Ix i => GHC.Arr.Ix (Combinatorics.CardPairs.CardCount i)
instance GHC.Classes.Ord i => GHC.Classes.Ord (Combinatorics.CardPairs.CardCount i)
instance GHC.Classes.Eq i => GHC.Classes.Eq (Combinatorics.CardPairs.CardCount i)
instance GHC.Show.Show Combinatorics.CardPairs.Card
instance GHC.Enum.Enum Combinatorics.CardPairs.Card
instance GHC.Classes.Ord Combinatorics.CardPairs.Card
instance GHC.Classes.Eq Combinatorics.CardPairs.Card

module Combinatorics.BellNumbers
bellRec :: Num a => [a]
bellSeries :: (Floating a, Enum a) => Int -> a
