-- 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:
--
--
-- - exact-combinatorics: Efficient computations of large
-- combinatoric numbers.
-- - combinat: Library for a similar purpose with a different
-- structure and selection of problems.
--
@package combinatorial
@version 0.1.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]]
-- | nodeDepth !! n !! k is the absolute frequency of nodes with
-- depth k in trees with n nodes.
nodeDepth :: [[Integer]]
-- | nodeDegree !! n !! k 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 prodLinearFactors.
pentagonalPowerSeries :: [Integer]
numPartitions :: [Integer]
-- | Give all partitions of the natural number n with summands which are at
-- least k. Not quite correct for k>n.
partitionsInc :: Integral a => a -> a -> [[a]]
partitionsDec :: Integral a => a -> a -> [[a]]
-- | type Int is needed because of list node indexing
--
--
-- QC.forAll (QC.choose (1,10)) $ \k -> QC.forAll (QC.choose (0,50)) $ \n -> Parts.partitionsInc k n == Parts.allPartitionsInc !! k !! n
--
--
--
-- equating (take 30) (map genericLength (Parts.allPartitionsInc !! 1)) Parts.numPartitions
--
allPartitionsInc :: [[[[Int]]]]
-- |
-- QC.forAll (QC.choose (0,100)) Parts.propInfProdLinearFactors
--
propInfProdLinearFactors :: Int -> Bool
-- |
-- Parts.propPentagonalPowerSeries 1000
--
propPentagonalPowerSeries :: Int -> Bool
-- |
-- Parts.propPentagonalsDifP 10000
--
propPentagonalsDifP :: Int -> Bool
-- |
-- Parts.propPentagonalsDifN 10000
--
propPentagonalsDifN :: 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 combinat
-- package.
module Combinatorics
-- | Generate list of all permutations of the input list. The list is
-- sorted lexicographically.
--
--
-- >>> Comb.permute "abc"
-- ["abc","acb","bac","bca","cab","cba"]
--
-- >>> Comb.permute "aabc"
-- ["aabc","aacb","abac","abca","acab","acba","aabc","aacb","abac","abca","acab","acba","baac","baca","baac","baca","bcaa","bcaa","caab","caba","caab","caba","cbaa","cbaa"]
--
--
--
-- QC.forAll (take 6 <$> QC.arbitrary :: QC.Gen [Int]) $ \xs -> allEqual $ map (\p -> sort (p xs)) $ Comb.permute : Comb.permuteFast : Comb.permuteShare : []
--
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 permute.
permuteFast :: [a] -> [[a]]
-- | All permutations share as much suffixes as possible. The reversed
-- permutations are sorted lexicographically.
permuteShare :: [a] -> [[a]]
-- |
-- >>> Comb.permuteRep [('a',2), ('b',1), ('c',1)]
-- ["aabc","aacb","abac","abca","acab","acba","baac","baca","bcaa","caab","caba","cbaa"]
--
--
--
-- QC.forAll (genPermuteRep 7) $ \xs -> let perms = Comb.permuteRep $ Key.nub fst xs in perms == nub perms
--
--
--
-- QC.forAll (genPermuteRep 10) $ \xs -> let perms = Comb.permuteRep $ Key.nub fst xs in List.sort perms == Set.toList (Set.fromList perms)
--
--
--
-- QC.forAll (genPermuteRep 10) $ isAscending . Comb.permuteRep . Key.nub fst . sort
--
--
--
-- QC.forAll (QC.choose (0,10)) $ \n k -> Comb.choose n k == Comb.permuteRep [(False, n-k), (True, k)]
--
permuteRep :: [(a, Int)] -> [[a]]
-- |
-- >>> map (map (\b -> if b then 'x' else '.')) $ Comb.choose 5 3
-- ["..xxx",".x.xx",".xx.x",".xxx.","x..xx","x.x.x","x.xx.","xx..x","xx.x.","xxx.."]
--
-- >>> map (map (\b -> if b then 'x' else '.')) $ Comb.choose 3 5
-- []
--
--
--
-- QC.forAll (QC.choose (0,10)) $ \n k -> all (\x -> n == length x && k == length (filter id x)) (Comb.choose n k)
--
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".
--
--
-- >>> Comb.variateRep 2 "abc"
-- ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
--
variateRep :: Int -> [a] -> [[a]]
-- | Generate all choices of n elements out of the list x without
-- repetitions.
--
--
-- >>> Comb.variate 2 "abc"
-- ["ab","ac","ba","bc","ca","cb"]
--
-- >>> Comb.variate 2 "abcd"
-- ["ab","ac","ad","ba","bc","bd","ca","cb","cd","da","db","dc"]
--
-- >>> Comb.variate 3 "abcd"
-- ["abc","abd","acb","acd","adb","adc","bac","bad","bca","bcd","bda","bdc","cab","cad","cba","cbd","cda","cdb","dab","dac","dba","dbc","dca","dcb"]
--
--
--
-- QC.forAll genVariate $ \xs -> Comb.variate (length xs) xs == Comb.permute xs
--
--
--
-- \xs -> equating (take 1000) (Comb.variate (length xs) xs) (Comb.permute (xs::String))
--
variate :: Int -> [a] -> [[a]]
-- | Generate all choices of n elements out of the list x respecting the
-- order in x and without repetitions.
--
--
-- >>> Comb.tuples 2 "abc"
-- ["ab","ac","bc"]
--
-- >>> Comb.tuples 2 "abcd"
-- ["ab","ac","ad","bc","bd","cd"]
--
-- >>> Comb.tuples 3 "abcd"
-- ["abc","abd","acd","bcd"]
--
tuples :: Int -> [a] -> [[a]]
-- |
-- >>> Comb.partitions "abc"
-- [("abc",""),("bc","a"),("ac","b"),("c","ab"),("ab","c"),("b","ac"),("a","bc"),("","abc")]
--
--
--
-- QC.forAll genVariate $ \xs -> length (Comb.partitions xs) == 2 ^ length xs
--
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 n-element sets into k non-empty
-- subsets. http://oeis.org/A048993
--
--
-- >>> Comb.rectifications 4 "abc"
-- ["aabc","abac","abbc","abca","abcb","abcc"]
--
-- >>> map (length . uncurry Comb.rectifications) $ do x<-[0..10]; y<-[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]
--
--
--
-- QC.forAll (QC.choose (0,7)) $ \k xs -> isAscending . Comb.rectifications k . nub . sort $ (xs::String)
--
rectifications :: Int -> [a] -> [[a]]
-- | Their number is k^n.
setPartitions :: Int -> [a] -> [[[a]]]
-- | All ways of separating a list of terms into pairs. All partitions are
-- given in a canonical form, sorted lexicographically. The canonical
-- form is: The list of pairs is ordered with respect to the first pair
-- members, and the elements in each pair are ordered. The order is
-- implied by the order in the input list.
--
-- http://oeis.org/A123023
pairPartitions :: [a] -> [[(a, a)]]
-- |
-- chooseUnrank n k i == choose n k !! i
--
--
--
-- QC.forAll (QC.choose (0,10)) $ \n k -> map (Comb.chooseUnrank n k) [0 .. Comb.binomial n k - 1] == Comb.choose n k
--
--
--
-- QC.forAll genChooseIndex $ \(n,k,i) -> Comb.chooseRank (Comb.chooseUnrank n k i) == (n, k, i)
--
--
--
-- \bs -> uncurry3 Comb.chooseUnrank (Comb.chooseRank bs :: (Integer, Integer, Integer)) == bs
--
chooseUnrank :: Integral a => a -> a -> a -> [Bool]
chooseUnrankMaybe :: Int -> Int -> Int -> Maybe [Bool]
-- | https://en.wikipedia.org/wiki/Combinatorial_number_system
chooseRank :: Integral a => [Bool] -> (a, a, a)
-- |
-- QC.forAll (take 8 <$> QC.arbitrary) $ \xs -> length (Comb.permute xs) == Comb.factorial (length (xs::String))
--
--
--
-- QC.forAll (take 6 <$> QC.arbitrary) $ \xs -> sum (map sum (Comb.permute xs)) == sum xs * Comb.factorial (length xs)
--
factorial :: Integral a => a -> a
-- | Pascal's triangle containing the binomial coefficients.
--
--
-- QC.forAll (QC.choose (0,12)) $ \n k -> length (Comb.choose n k) == Comb.binomial n k
--
--
--
-- QC.forAll genBinomial $ \(n,k) -> let (q, r) = divMod (Comb.factorial n) (Comb.factorial k * Comb.factorial (n-k)) in r == 0 && Comb.binomial n k == q
--
--
--
-- QC.forAll (take 16 <$> QC.arbitrary) $ \xs k -> length (Comb.tuples k xs) == Comb.binomial (length (xs::String)) k
--
binomial :: Integral a => a -> a -> a
binomialSeq :: Integral a => a -> [a]
binomialGen :: (Integral a, Fractional b) => b -> a -> b
binomialSeqGen :: Fractional b => b -> [b]
-- |
-- QC.forAll (genPermuteRep 10) $ \xs -> length (Comb.permuteRep xs) == Comb.multinomial (map snd xs)
--
--
--
-- QC.forAll (QC.listOf $ QC.choose (0,300::Integer)) $ \xs -> Comb.multinomial xs == Comb.multinomial (sort xs)
--
multinomial :: Integral a => [a] -> a
-- |
-- equalFuncList Comb.factorial Comb.factorials 1000
--
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.
--
--
-- equalFuncList2 Comb.binomial Comb.binomials 100
--
binomials :: Num a => [[a]]
-- | catalanNumber n computes the number of binary trees with
-- n nodes.
catalanNumber :: Integer -> Integer
-- | Compute the sequence of Catalan numbers by recurrence identity. It is
-- catalanNumbers !! n == catalanNumber n
--
--
-- equalFuncList Comb.catalanNumber Comb.catalanNumbers 1000
--
catalanNumbers :: Num a => [a]
derangementNumber :: Integer -> Integer
-- | Number of fix-point-free permutations with n elements.
--
-- http://oeis.org/A000166
--
--
-- equalFuncList Comb.derangementNumber Comb.derangementNumbers 1000
--
derangementNumbers :: Num a => [a]
-- | Number of partitions of an n element set into k
-- non-empty subsets. Known as Stirling numbers
-- http://oeis.org/A048993.
--
--
-- QC.forAll (QC.choose (0,10000)) $ \k -> QC.forAll (take 7 <$> QC.arbitrary) $ \xs -> length (Comb.setPartitions k xs) == (Comb.setPartitionNumbers !! length (xs::String) ++ repeat 0) !! k
--
--
--
-- QC.forAll (QC.choose (0,7)) $ \k xs -> length (Comb.rectifications k xs) == (Comb.setPartitionNumbers !! k ++ repeat 0) !! length (xs::String)
--
setPartitionNumbers :: Num a => [[a]]
-- | surjectiveMappingNumber n k computes the number of surjective
-- mappings from a n element set to a k element set.
--
-- http://oeis.org/A019538
surjectiveMappingNumber :: Integer -> Integer -> Integer
-- |
-- equalFuncList2 Comb.surjectiveMappingNumber Comb.surjectiveMappingNumbers 20
--
surjectiveMappingNumbers :: Num a => [[a]]
fibonacciNumber :: Integer -> Integer
-- | Number of possibilities to compose a 2 x n rectangle of n bricks.
--
--
-- ||| |-- --|
-- ||| |-- --|
--
--
--
-- equalFuncList Comb.fibonacciNumber Comb.fibonacciNumbers 10000
--
fibonacciNumbers :: [Integer]
module Combinatorics.Permutation.WithoutSomeFixpoints
-- | enumerate n xs list all permutations of xs where the
-- first n 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]]
-- | http://oeis.org/A047920
--
--
-- QC.forAll genPermutationWOFP $ \(k,xs) -> PermWOFP.numbers !! length xs !! k == length (PermWOFP.enumerate k xs)
--
--
--
-- QC.forAll (QC.choose (0,100)) $ \k -> Comb.factorial (toInteger k) == PermWOFP.numbers !! k !! 0
--
--
--
-- QC.forAll (QC.choose (0,100)) $ \k -> Comb.derangementNumber (toInteger k) == PermWOFP.numbers !! k !! k
--
numbers :: Num a => [[a]]
-- | Number of possible games as described in
-- http://projecteuler.net/problem=306.
module Combinatorics.PaperStripGame
numbersOfGames :: [Int]
numbersOfGamesSeries :: [Integer]
treeOfGames :: Int -> Tree [Int]
module Combinatorics.Mastermind
-- | Cf. board-games package.
data Eval
Eval :: Int -> Eval
[black, white] :: Eval -> Int
-- | Given the code and a guess, compute the evaluation.
--
--
-- >>> filter ((Mastermind.Eval 2 0 ==) . Mastermind.evaluate "aabbb") $ replicateM 5 ['a'..'c']
-- ["aaaaa","aaaac","aaaca","aaacc","aacaa","aacac","aacca","aaccc","acbcc","accbc","acccb","cabcc","cacbc","caccb","ccbbc","ccbcb","cccbb"]
--
evaluate :: Ord a => [a] -> [a] -> Eval
evaluateAll :: Ord a => [[a]] -> [a] -> Map Eval Int
formatEvalHistogram :: Map Eval Int -> String
-- | numberDistinct n k b w computes the number of matching codes,
-- given that all codes have distinct symbols. n is the alphabet
-- size, k the width of the code, b the number of black
-- evaluation sticks and w the number of white evaluation
-- sticks.
--
--
-- QC.forAll genMastermindDistinct $ \(n,k,b,w) -> let alphabet = take n ['a'..]; code = take k alphabet in Mastermind.numberDistinct n k b w == (genericLength $ filter ((Mastermind.Eval b w ==) . Mastermind.evaluate code) $ Comb.variate k alphabet)
--
numberDistinct :: Int -> Int -> Int -> Int -> Integer
-- |
-- QC.forAll genMastermindDistinct $ \(n,k,_b,w) -> Mastermind.numberDistinctWhite n k w == Mastermind.numberDistinct n k 0 w
--
numberDistinctWhite :: 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
-- | Compute how often it happens that a Queen and a King are adjacent in a
-- randomly ordered card set.
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 q, start with king k)
--
--
-- allEqual [CardPairs.possibilitiesCardsBorderNaive (CardCount 2 3 5), CardPairs.possibilitiesCardsBorderDynamic (CardCount 5 5 5) ! (CardCount 2 3 5), CardPairs.possibilitiesCardsBorder2Dynamic (CardCount 5 5 5) ! (CardCount 2 3 5)]
--
--
--
-- QC.forAll genCardCount $ \cc -> allEqual [CardPairs.possibilitiesCardsBorderNaive cc, CardPairs.possibilitiesCardsBorderDynamic cc ! cc, CardPairs.possibilitiesCardsBorder2Dynamic cc ! cc]
--
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
exampleOutput :: IO ()
adjacentCouplesSmall :: [[Card]]
allPossibilitiesSmall :: [[Card]]
allPossibilitiesMedium :: [[Card]]
allPossibilitiesSkat :: [[Card]]
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
instance GHC.Show.Show i => GHC.Show.Show (Combinatorics.CardPairs.CardCount i)
instance GHC.Ix.Ix i => GHC.Ix.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)
module Combinatorics.BellNumbers
-- | List of Bell numbers computed with the recursive formula given in
-- Wurzel 2004-06, page 136
bellRec :: Num a => [a]
-- |
-- equalFuncList (\k -> round (Bell.bellSeries (fromInteger k) :: Double)) (Bell.bellRec :: [Integer]) 20
--
bellSeries :: (Floating a, Enum a) => Int -> a