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 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.

# Permutations

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

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

For example, `permutations [(`

, whereas `a`

,1), (`b`

,2)] ==
["abb","bba","bab"]```
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

vPartitions :: Vec -> [MultiSet Vec]Source

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