multiset-comb-0.2: Combinatorial algorithms over multisets

Math.Combinatorics.Multiset

Contents

Description

Efficient combinatorial algorithms over multisets, including generating all permutations, partitions, subsets, cycles, and other combinatorial structures based on multisets. Note that an `Eq` or `Ord` instance on the elements is not required; the algorithms are careful to keep track of which things are (by construction) equal to which other things, so equality testing is not needed.

Synopsis

The `Multiset` type

newtype Multiset a Source

A multiset is represented as a list of (element, count) pairs. We maintain the invariants that the counts are always positive, and no element ever appears more than once.

Constructors

 MS FieldstoCounts :: [(a, Count)]

Instances

 Functor Multiset Show a => Show (Multiset a)

consMS :: (a, Count) -> Multiset a -> Multiset aSource

Add an element with multiplicity to a multiset. Precondition: the new element is distinct from all elements already in the multiset.

(+:) :: (a, Count) -> Multiset a -> Multiset aSource

A convenient shorthand for `consMS`.

Conversions

toList :: Multiset a -> [a]Source

Convert a multiset to a list.

fromList :: Ord a => [a] -> Multiset aSource

Efficiently convert a list to a multiset, given an `Ord` instance for the elements. This method is provided just for convenience. you can also use `fromListEq` with only an `Eq` instance, or construct `Multiset`s directly using `fromCounts`.

fromListEq :: Eq a => [a] -> Multiset aSource

Convert a list to a multiset, given an `Eq` instance for the elements.

fromDistinctList :: [a] -> Multiset aSource

Make a multiset with one copy of each element from a list of distinct elements.

fromCounts :: [(a, Count)] -> Multiset aSource

Construct a `Multiset` from a list of (element, count) pairs. Precondition: the counts must all be positive, and there must not be any duplicate elements.

getCounts :: Multiset a -> [Count]Source

Extract just the element counts from a multiset, forgetting the elements.

Operations

disjUnion :: Multiset a -> Multiset a -> Multiset aSource

Form the disjoint union of two multisets; i.e. we assume the two multisets share no elements in common.

disjUnions :: [Multiset a] -> Multiset aSource

Form the disjoint union of a collection of multisets. We assume that the multisets all have distinct elements.

Permutations

permutations :: Multiset a -> [[a]]Source

List all the distinct permutations of the elements of a multiset.

For example, ```permutations (fromList "abb") == ["abb","bba","bab"]```, whereas ```Data.List.permutations "abb" == ["abb","bab","bba","bba","bab","abb"]```. This function is equivalent to, but much more efficient than, `nub . Data.List.permutations`, and even works when the elements have no `Eq` instance.

Note that this is a specialized version of `permutationsRLE`, where each run has been expanded via `replicate`.

permutationsRLE :: Multiset a -> [[(a, Count)]]Source

List all the distinct permutations of the elements of a multiset, with each permutation run-length encoded. (Note that the run-length encoding is a natural byproduct of the algorithm used, not a separate postprocessing step.)

For example, ```permutationsRLE [(a,1), (b,2)] == [[(a,1),(b,2)],[(b,2),(a,1)],[(b,1),(a,1),(b,1)]]```.

(Note that although the output type is newtype-equivalent to `[Multiset a]`, we don't call it that since the output may violate the `Multiset` invariant that no element should appear more than once. And indeed, morally this function does not output multisets at all.)

Partitions

type Vec = [Count]Source

Element count vector.

Generate all vector partitions, representing each partition as a multiset of vectors.

This code is a slight generalization of the code published in

See that article for a detailed discussion of the code and how it works.

partitions :: Multiset a -> [Multiset (Multiset a)]Source

Efficiently generate all distinct multiset partitions. Note that each partition is represented as a multiset of parts (each of which is a multiset) in order to properly reflect the fact that some parts may occur multiple times.

Submultisets

splits :: Multiset a -> [(Multiset a, Multiset a)]Source

Generate all splittings of a multiset into two submultisets, i.e. all size-two partitions.

kSubsets :: Count -> Multiset a -> [Multiset a]Source

Generate all size-k submultisets.

Cycles

cycles :: Multiset a -> [[a]]Source

Generate all distinct cycles, aka necklaces, with elements taken from a multiset. See J. Sawada, "A fast algorithm to generate necklaces with fixed content", J. Theor. Comput. Sci. 301 (2003) pp. 477-489.

Given the ordering on the elements of the multiset based on their position in the multiset representation (with "smaller" elements first), in `map reverse (cycles m)`, each generated cycle is lexicographically smallest among all its cyclic shifts, and furthermore, the cycles occur in reverse lexicographic order. (It's simply more convenient/efficient to generate the cycles reversed in this way, and of course we get the same set of cycles either way.)

For example, ```cycles (fromList "aabbc") == ["cabba","bcaba","cbaba","bbcaa","bcbaa","cbbaa"]```.

Miscellaneous

sequenceMS :: Multiset [a] -> [Multiset a]Source

Take a multiset of lists, and select one element from each list in every possible combination to form a list of multisets. We assume that all the list elements are distinct.