Combinatorics

Count and create combinatorial objects. Also see combinat package.

Documentation

permute :: [a] -> [[a]]

Generate list of all permutations of the input list. The list is sorted lexicographically.

permuteFast :: [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.

permuteShare :: [a] -> [[a]]

All permutations share as much suffixes as possible. The reversed permutations are sorted lexicographically.

permuteRep :: [(a, Int)] -> [[a]]

choose :: Int -> Int -> [[Bool]]

variateRep :: Int -> [a] -> [[a]]

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".

variate :: Int -> [a] -> [[a]]

Generate all choices of n elements out of the list x without repetitions. It holds variate (length xs) xs == permute xs

tuples :: Int -> [a] -> [[a]]

Generate all choices of n elements out of the list x respecting the order in x and without repetitions.

partitions :: [a] -> [([a], [a])]

rectifications :: Int -> [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]

setPartitions :: Int -> [a] -> [[[a]]]

Their number is k^n.

chooseUnrank :: Integral a => a -> a -> a -> [Bool]

chooseUnrank n k i == choose n k !! i

chooseUnrankMaybe :: Int -> Int -> Int -> Maybe [Bool]

chooseRank :: Integral a => [Bool] -> (a, a, a)

https://en.wikipedia.org/wiki/Combinatorial_number_system

factorial :: Integral a => a -> a

binomial :: Integral a => a -> a -> a

Pascal's triangle containing the binomial coefficients.

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]

binomials :: 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.

catalanNumber :: Integer -> Integer

catalanNumber n computes the number of binary trees with n nodes.

catalanNumbers :: Num a => [a]

Compute the sequence of Catalan numbers by recurrence identity. It is catalanNumbers !! n == catalanNumber n

derangementNumber :: Integer -> Integer

derangementNumbers :: Num a => [a]

Number of fix-point-free permutations with n elements.

http://oeis.org/A000166

setPartitionNumbers :: Num a => [[a]]

Number of partitions of an n element set into k non-empty subsets. Known as Stirling numbers http://oeis.org/A048993.

surjectiveMappingNumber :: Integer -> Integer -> Integer

surjectiveMappingNumber n k computes the number of surjective mappings from a n element set to a k element set.

http://oeis.org/A019538

surjectiveMappingNumbers :: Num a => [[a]]

fibonacciNumber :: Integer -> Integer

fibonacciNumbers :: [Integer]

Number of possibilities to compose a 2 x n rectangle of n bricks.

 |||   |--   --|
 |||   |--   --|