Efficient combinatorial algorithms to generate all permutations
and partitions of a multiset. Note that an
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.
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.
List all the distinct permutations of the elements of a multiset.
permutations [(, whereas
"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
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.)
(Note that although the output type is equivalent to
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.)
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.