-- 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: -- -- @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]] -- | 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]] -- | it shall be k>0 && n>=0 ==> 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 combinat -- 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 permute. 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 variate (length xs) xs == permute xs 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 n-element sets into k non-empty -- subsets. http://oeis.org/A048993 -- -- 
--   *Combinatorics> map (length . uncurry 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]
--
rectifications :: Int -> [a] -> [[a]] -- | Their number is k^n. setPartitions :: Int -> [a] -> [[[a]]] -- | 
--   chooseUnrank n k i == choose n k !! i
--
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) 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]] -- | 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 catalanNumbers :: Num a => [a] derangementNumber :: Integer -> Integer -- | Number of fix-point-free permutations with n elements. -- -- http://oeis.org/A000166 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. 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 surjectiveMappingNumbers :: Num a => [[a]] fibonacciNumber :: Integer -> Integer -- | Number of possibilities to compose a 2 x n rectangle of n bricks. -- -- 
--   |||   |--   --|
--   |||   |--   --|
--
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 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. 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. 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 q, start with king k) 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