| 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
- encodeMultiset :: [Int] -> ((Int, Int), BitVec)
- decodeMultiset :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)
- rankMultiset :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankMultiset :: (Int, Int) -> Integer -> [Int]
- multichoose :: Int -> Int -> Integer
- encodeMultiset1 :: [Int] -> ((Int, Int), BitVec)
- decodeMultiset1 :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)
- rankMultiset1 :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankMultiset1 :: (Int, Int) -> Integer -> [Int]
- multichoose1 :: 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
stripped of the permutation's code. 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 stripped of the
permutation's code. 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 \((n,k)\) where \(n\) is the
length of the list and \(k\) is the number of True values, and the
code as a bit vector.
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 stripped of the combination's code. 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 \((n,k)\) where \(n\) is the length of the list and
\(k\) is the number of True values, 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\).
Multisets
A multiset is a set where elements may appear more than once. The number of multisets of size \(n\) with at most \(m\) distinct elements is equivalent to a certain combination when counting the number of ways to distribute \(n\) identical elements to \(m\) bins (see stars and bars): \[ {n + m - 1 \choose m - 1} \] or referred to as the "multiset coefficient": \[ \left(\!\!{m \choose n}\!\!\right) = {m + n - 1 \choose n} = \frac{(n + m - 1)!}{n!(m-1)!} \]
encodeMultiset :: [Int] -> ((Int, Int), BitVec) Source #
Encode a multiset specified as a list of non-negative element counts into a bit vector. Returns parameters \((n,m)\) where \(n\) is the total number of elements and \(m\) is the number of distinct elements, and the code as a bit vector.
decodeMultiset :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec) Source #
Try to decode a multiset at the head of a bit vector, given
parameters \((n,m)\) where \(n\) is the total number of elements and
\(m\) is the number of distinct elements. If successful, returns the
decoded multiset as a list of non-negative element counts and the
remainder of the BitVec stripped of the multiset's code. Returns
Nothing if the bit vector doesn't contain enough bits to specify a
multiset of the given parameters.
rankMultiset :: [Int] -> ((Int, Int), (Integer, Integer)) Source #
Rank a multiset specified as a list of non-negative element counts. Returns the \((n,m)\) parameters (where \(n\) is the total number of elements and \(m\) is the number of distinct elements), the rank and the number of multisets with those parameters.
unrankMultiset :: (Int, Int) -> Integer -> [Int] Source #
Reconstruct a multiset given parameters \((n,m)\) and a rank.
multichoose :: Int -> Int -> Integer Source #
m computes the number of multisets with \(n\)
total elements with at most \(m\) distinct elements, or the "multiset
coefficent": \[ \left(\!\!{m \choose n}\!\!\right) = \frac{(m + n -
1)!}{n!(m-1)!} \]`multichoose` n
Multisets with Positive Counts
A special class of multisets where each of the \(m\) distinct elements appears at least once.
encodeMultiset1 :: [Int] -> ((Int, Int), BitVec) Source #
Encode a multiset specified as a list of positive bin counts into a bit vector. Returns parameters \((n,m)\) where \(n\) is the total number of elements and \(m\) is the number of distinct elements, and the code as a bit vector.
decodeMultiset1 :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec) Source #
Try to decode a multiset at the head of a bit vector, given
parameters \((n,m)\), where \(n\) is the total number of elements,
\(m\) is the number of distinct elements and \(n \geq m\). If
successful, returns the decoded multiset as a list of positive
element counts and the remainder of the BitVec with the multiset's
code removed. Returns Nothing if the bit vector doesn't contain
enough bits to specify such a multiset of the given parameters.
rankMultiset1 :: [Int] -> ((Int, Int), (Integer, Integer)) Source #
Rank a multiset specified as a list of positive element counts. Returns the \((n,m)\) parameters (where \(n\) is the total number of elements and \(m\) is the number of distinct elements), the rank and the number of multisets with those parameters.
unrankMultiset1 :: (Int, Int) -> Integer -> [Int] Source #
Reconstruct a multiset given parameters \((n,m)\) and a rank.
multichoose1 :: Int -> Int -> Integer Source #
m computes the number of multisets with \(n\)
total elements and exactly \(m\) distinct elements. This is
equivalent to `multichoose1` nm or: \[ \left(\!\!{m \choose
n - m}\!\!\right) = \frac{(n - 1)!}{(n-m)!(m-1)!} \]`multichoose` (n - m)