-- 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.0 module Combinatorics.TreeDepth -- | nodeDepth !! n !! k is the absolute frequency of nodes with -- depth k in trees with n nodes. nodeDepth :: [[Integer]] nodeDepthIt :: Integer -> [Integer] -> [Integer] -- | treeDepth !! n !! m !! k is the absolute frequency of nodes -- with depth k in trees with n nodes and depth m. This can't work - the -- function carries not enough information for recursive definition. -- treeDepth :: [[[Integer]]] treeDepth = iterate (ls -> zipWith -- treeDepthIt ([[]]++ls) (ls++[[0]])) [[1]] -- -- treeDepthIt :: [Integer] -> [Integer] -> [Integer] treeDepthIt -- nm0 nm1 = foldl1 add [scale (if null nm0 then 0 else last nm0) (nm0 ++ -- [1]), scale (sum (init nm1)) nm1, 0 : init nm1] -- -- Trees are abstracted to lists of integers, where each integer denotes -- the number of nodes in the corresponding depth of the tree. The number -- associated with each tree is the frequency of this kind of tree on -- random tree generation. type TreeFreq = Map [Integer] Integer treeDepth :: [Rational] treeDepthSeq :: [[Integer]] treePrototypes :: [TreeFreq] extendTree :: [Integer] -> [[Integer]] treeDepthIt :: TreeFreq -> TreeFreq -- | nodeDegree !! n !! k is the number of nodes with outdegree k -- in a n-node tree. nodeDegreeProb :: [[Rational]] nodeDegree :: [[Integer]] nodeDegreeIt :: Integer -> Integer -> [Integer] -> [Integer] -- | expected value of node degree nodeDegreeExpect :: [Rational] nodeDegreeExpectTrans :: Integer -> [Integer] -> [Integer] nodeDegreeExpectAux0 :: [Integer] nodeDegreeExpectAux1 :: [Integer] 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 -- | 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 -- | We only track the number taken by player A because player B will -- automatically have the complement set. gameRound :: (Set Int, Set Int) -> [(Set Int, Set Int)] possibilities :: Int -> Set (Set Int) numberOfPossibilities :: [Int] -- | 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]] permuteMSL :: [a] -> [[a]] runPermuteRep :: ([(a, Int)] -> [[a]]) -> [(a, Int)] -> [[a]] permuteRep :: [(a, Int)] -> [[a]] permuteRepM :: [(a, Int)] -> [[a]] choose :: Int -> Int -> [[Bool]] chooseMSL :: 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]] variateRepMSL :: 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]] variateMSL :: 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]] tuplesMSL :: Int -> [a] -> [[a]] tuplesRec :: 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]]] -- | 
--   chooseFromIndex n k i == choose n k !! i
--
chooseFromIndex :: Integral a => a -> a -> a -> [Bool] chooseFromIndexList :: Integral a => a -> a -> a -> [Bool] chooseFromIndexMaybe :: Int -> Int -> Int -> Maybe [Bool] chooseToIndex :: 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] derangementNumbersAlt :: Num a => [a] derangementNumbersInclExcl :: 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]] surjectiveMappingNumbersStirling :: Num a => [[a]] fibonacciNumber :: Integer -> Integer -- | Number of possibilities to compose a 2 x n rectangle of n bricks. -- -- 
--   |||   |--   --|
--   |||   |--   --|
--
fibonacciNumbers :: [Integer] module Combinatorics.BellNumbers bellRec :: Num a => [a] bellSeries :: (Floating a, Enum a) => Int -> a module Combinatorics.CardPairs type CardSet a = [(a, Int)] data Card Other :: Card Queen :: Card King :: Card charFromCard :: Card -> Char removeEach :: StateT (CardSet a) [] a normalizeSet :: CardSet a -> CardSet a allPossibilities :: CardSet a -> [[a]] allPossibilitiesSmall :: [[Card]] allPossibilitiesMedium :: [[Card]] allPossibilitiesSkat :: [[Card]] adjacentCouple :: [Card] -> Bool adjacentCouplesSmall :: [[Card]] exampleOutput :: IO () -- | Candidate for utility-ht: sample :: (a -> b) -> [a] -> [(a, b)] data CardCount i CardCount :: i -> CardCount i [otherCount, queenCount, kingCount] :: CardCount i -> i possibilitiesCardsNaive :: CardCount Int -> Integer possibilitiesCardsDynamic :: CardCount Int -> Array (CardCount Int) Integer sumCard :: Num i => CardCount i -> i -- | 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) testCardsBorderDynamic :: (CardCount Integer, CardCount Integer, CardCount Integer) numberOfAllPossibilities :: CardCount Int -> 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 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 -- | Number of possible games as described in -- http://projecteuler.net/problem=306. module Combinatorics.PaperStripGame cutEverywhere0 :: [Int] -> [[Int]] cutEverywhere1 :: [Int] -> [[Int]] cutPart :: Int -> [(Int, Int)] treeOfGames :: Int -> Tree [Int] lengthOfGames :: Int -> [Int] numbersOfGames :: [Int] numbersOfGamesSeries :: [Integer] module Combinatorics.Permutation.WithoutSomeFixpoints -- | enumerate n xs list all permutations of xs where the -- first n elements do not keep there position (i.e. are no -- fixpoints). -- -- Naive but comprehensible implementation. enumerate :: (Eq a) => Int -> [a] -> [[a]] -- | http://oeis.org/A047920 numbers :: (Num a) => [[a]] 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