| 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
- rankMultisetPermutation :: Ord a => [a] -> ([(a, Int)], (Integer, Integer))
- unrankMultisetPermutation :: Ord a => [(a, Int)] -> Integer -> [a]
- multinomial :: [Int] -> Integer
- rankPermutation :: Ord a => [a] -> (Integer, Integer)
- unrankPermutation :: Ord a => [a] -> Integer -> [a]
- rankCombination :: [Bool] -> ((Int, Int), (Integer, Integer))
- unrankCombination :: (Int, Int) -> Integer -> [Bool]
- choose :: Int -> Int -> Integer
- rankDistribution :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankDistribution :: (Int, Int) -> Integer -> [Int]
- rankDistribution1 :: [Int] -> ((Int, Int), (Integer, Integer))
- unrankDistribution1 :: (Int, Int) -> Integer -> [Int]
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 \]
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!\).
rankPermutation :: Ord a => [a] -> (Integer, Integer) Source #
Rank a permutation. Returns the rank and the total number of permutations of sets with that size ( \(n!\) ).
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)!} \]
rankCombination :: [Bool] -> ((Int, Int), (Integer, Integer)) Source #
Rank a combination in the form of a list of booleans. 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 ).
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.
Non-Empty Distributions
The class of distributions that have at least one element per bin.
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.