Math.Combinatorics.Multiset

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.

The MultiSet type

type Count = Int

type MultiSet a = [(a, Count)]

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]

Convert a multiset to a list.

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

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

Permutations

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

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)]]

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]

Element count vector.

vPartitions :: Vec -> [MultiSet Vec]

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

This code is a slight generalization of the code published in

Brent Yorgey. "Generating Multiset Partitions". In: The Monad.Reader, Issue 8, September 2007. http://www.haskell.org/sitewiki/images/d/dd/TMR-Issue8.pdf

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

partitions :: MultiSet a -> [MultiSet (MultiSet a)]

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.