| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Codec.Arithmetic.Combinatorics
Description
Optimal codes for combinatorial objects.
The integer on which a combinatorial objects is mapped is typically called its rank. Below are implementations of ranking and unranking algorithms for the indexes of common combinatorial objects in the lexicographic enumeration of objects of the same parameters.
Synopsis
- encodeMultisetPermutation :: Ord a => [a] -> ([(a, Int)], BitVec)
- decodeMultisetPermutation :: Ord a => [(a, Int)] -> BitVec -> Maybe ([a], BitVec)
- rankMultisetPermutation :: Ord a => [a] -> ([(a, Int)], (Integer, Integer))
- unrankMultisetPermutation :: Ord a => [(a, Int)] -> Integer -> [a]
- multinomial :: [Int] -> Integer
- encodePermutation :: Ord a => [a] -> BitVec
- decodePermutation :: Ord a => [a] -> BitVec -> Maybe ([a], BitVec)
- rankPermutation :: Ord a => [a] -> (Integer, Integer)
- unrankPermutation :: Ord a => [a] -> Integer -> [a]
- factorial :: Int -> Integer
- encodeCombination :: [Bool] -> ((Int, Int), BitVec)
- decodeCombination :: (Int, Int) -> BitVec -> Maybe ([Bool], BitVec)
- rankCombination :: [Bool] -> ((Int, Int), (Integer, Integer))
- unrankCombination :: (Int, Int) -> Integer -> [Bool]
- choose :: Int -> Int -> Integer
- encodeDistribution :: [Int] -> ((Int, Int), BitVec)
- decodeDistribution :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)
- rankDistribution :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankDistribution :: (Int, Int) -> Integer -> [Int]
- countDistributions :: Int -> Int -> Integer
- encodeDistribution1 :: [Int] -> ((Int, Int), BitVec)
- decodeDistribution1 :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)
- rankDistribution1 :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankDistribution1 :: (Int, Int) -> Integer -> [Int]
- countDistributions1 :: Int -> Int -> Integer
Multiset Permutations
Multiset permutations are ways to order the elements of a set where elements may appear more than once. The number of such permutations is equal to the multinomial coefficient with the same parameters: \[ {n \choose k_{1}, k_{2}, \ldots, k_{m}} = \frac{n!}{k_{1}! k_{2}! \cdots k_{m}!} ~~~~~\mathrm{where}~~~~~ n = \sum_i k_i \]
encodeMultisetPermutation :: Ord a => [a] -> ([(a, Int)], BitVec) Source #
Encode a multiset permutation into a bit vector. Returns the count of each element in the set and the code as a vector of length equal to the multinomial coefficient with those counts.
decodeMultisetPermutation :: Ord a => [(a, Int)] -> BitVec -> Maybe ([a], BitVec) Source #
Try to decode a multiset permutation at the head of a bit vector,
given the count of each element in the set. If successful, returns
the decoded multiset permutation and the remainder of the BitVec
with the permutation's code removed. Returns Nothing if the bit
vector doesn't contain enough bits to specify a multiset permutation
of the given parameters.
rankMultisetPermutation :: Ord a => [a] -> ([(a, Int)], (Integer, Integer)) Source #
Rank a multiset permutation. Returns the count of each element in the set, the rank and the total number of permutations with those counts (the multinomial coefficient).
unrankMultisetPermutation :: Ord a => [(a, Int)] -> Integer -> [a] Source #
Reconstruct a multiset permutation, given the count of each element in the set and a rank.
multinomial :: [Int] -> Integer Source #
Computes the multinomial coefficient given a list of counts \(k_i\).
Permutations
A permutation is an ordering of the objects of a set of distinct elements. The number of permutations of a set of \(n\) elements is \(n!\).
encodePermutation :: Ord a => [a] -> BitVec Source #
Encode a permutation into a bit vector of length equal to the factorial of the length of the given list.
decodePermutation :: Ord a => [a] -> BitVec -> Maybe ([a], BitVec) Source #
Try to decode a permutation at the head of a bit vector, given the
elements in the set that was permuted. If successful, returns the
decoded permutation and the remainder of the BitVec with the
permutation's code removed. Returns Nothing if the bit vector
doesn't contain enough bits to specify a permutation of a set of the
length of the given list of elements.
unrankPermutation :: Ord a => [a] -> Integer -> [a] Source #
Reconstruct a permutation given a set of elements and a rank. The order in which the elements of the set is given does not matter.
Combinations
A combination is a selection of \(k\) elements from a set of size \(n\). The number of combinations for parameters \(n\) and \(k\) is given by the binomial coefficient: \[ {n \choose k} = \frac{n!}{k! (n-k)!} \]
encodeCombination :: [Bool] -> ((Int, Int), BitVec) Source #
Encode a combination in the form of a list of booleans (chosen/not
chosen) into a bit vector. Returns the \((n,k)\) parameters (where
\(k\) is the number of True values and \(n\) is the total), and the
code as a vector of length equal to the binomial coefficient with
those parameters.
decodeCombination :: (Int, Int) -> BitVec -> Maybe ([Bool], BitVec) Source #
Try to decode a combination in the form of a list of booleans
(chosen/not chosen) at the head of a bit vector, given the parameters
\((n,k)\). If successful, returns the decoded combination and the
remainder of the BitVec with the combination's code
removed. Returns Nothing if the bit vector doesn't contain enough
bits to specify a combination of the given parameters.
rankCombination :: [Bool] -> ((Int, Int), (Integer, Integer)) Source #
Rank a combination in the form of a list of booleans (chosen/not
chosen). Returns the \((n,k)\) parameters (where \(k\) is the number
of True values and \(n\) is the total), the rank and the total
number of combinations with those parameters (the binomial
coefficient).
unrankCombination :: (Int, Int) -> Integer -> [Bool] Source #
Reconstruct a combination given parameters \((n,k)\) and a rank.
choose :: Int -> Int -> Integer Source #
Computes the binomial coefficent given parameters \(n\) and \(k\).
Distributions
A distribution (usually discussed under the name stars and bars) is a way to distribute \(n\) equal elements (stars) among \(k\) bins (i.e. \(k-1\) bars ).
encodeDistribution :: [Int] -> ((Int, Int), BitVec) Source #
Encode a distribution in the form of a list bin counts into a bit vector. Returns the \((n,k)\) parameters (where \(n\) is the total number of elements and \(k\) is the number of bins) and the code as a vector of length equal to the number of distributions with those parameters.
decodeDistribution :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec) Source #
Try to decode a distribution in the form of a list of bin counts at
the head of a bit vector, given the parameters \((n,k)\). If
successful, returns the decoded distribution and the remainder of the
BitVec with the distribution's code removed. Returns Nothing if
the bit vector doesn't contain enough bits to specify a distribution
of the given parameters.
rankDistribution :: [Int] -> ((Int, Int), (Integer, Integer)) Source #
Rank a distribution in the form of a list bin counts. Returns the \((n,k)\) parameters (where \(n\) is the total number of elements and \(k\) is the number of bins), the rank and the total number of distributions with those parameters.
unrankDistribution :: (Int, Int) -> Integer -> [Int] Source #
Reconstruct a distribution given parameters \((n,k)\) and a rank.
countDistributions :: Int -> Int -> Integer Source #
Computes the number of distributions that have the given parameters \(n\) and \(k\).
Non-Empty Distributions
The class of distributions that have at least one element per bin.
encodeDistribution1 :: [Int] -> ((Int, Int), BitVec) Source #
Encode a non-empty distribution in the form of a list bin counts into a bit vector. Returns the \((n,k)\) parameters (where \(n\) is the total number of elements and \(k\) is the number of bins) and the code as a vector of length equal to the number of distributions with those parameters.
decodeDistribution1 :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec) Source #
Try to decode a non-empty distribution in the form of a list of bin
counts at the head of a bit vector, given the parameters
\((n,k)\). If successful, returns the decoded distribution and the
remainder of the BitVec with the distribution's code
removed. Returns Nothing if the bit vector doesn't contain enough
bits to specify a non-empty distribution of the given parameters.
rankDistribution1 :: [Int] -> ((Int, Int), (Integer, Integer)) Source #
Rank a non-empty distribution in the form of a list bin counts. Returns the \((n,k)\) parameters (where \(n\) is the total number of elements and \(k\) is the number of bins), the rank and the total number of distributions with those parameters.