multiset-comb-0.1: Combinatorial operations on multisets

Math.Combinatorics.Multiset

Contents

Description

Efficient combinatorial algorithms to generate all permutations and partitions of a multiset. 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

type MultiSet a = [(a, Count)]Source

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

toList :: MultiSet a -> [a]Source

Convert a multiset to a list.

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

Convert a list to a multiset. This method is provided just for convenience; you can of course construct your own `MultiSet`s directly (especially if the type of the elements is not an instance of `Ord`).

# Permutations

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

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

For example, ```permutations [(a,1), (b,2)] == ["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 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