-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Combinatorial operations on multisets
--   
--   Efficiently generate all permutations and partitions of multisets.
@package multiset-comb
@version 0.1


-- | Efficient combinatorial algorithms to generate all permutations and
--   partitions of a multiset. Note that an <a>Eq</a> or <a>Ord</a>
--   instance on the elements is <i>not</i> 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.
module Math.Combinatorics.Multiset
type Count = Int

-- | 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.
type MultiSet a = [(a, Count)]

-- | Convert a multiset to a list.
toList :: MultiSet a -> [a]

-- | Convert a list to a multiset. This method is provided just for
--   convenience; you can of course construct your own <a>MultiSet</a>s
--   directly (especially if the type of the elements is not an instance of
--   <a>Ord</a>).
fromList :: (Ord a) => [a] -> MultiSet a

-- | List all the distinct permutations of the elements of a multiset.
--   
--   For example, <tt>permutations [(<tt>a</tt>,1), (<tt>b</tt>,2)] ==
--   ["abb","bba","bab"]</tt>, whereas <tt>Data.List.permutations "abb" ==
--   ["abb","bab","bba","bba","bab","abb"]</tt>. This function is
--   equivalent to, but <i>much</i> more efficient than, <tt>nub .
--   Data.List.permutations</tt>, and even works when the elements have no
--   <a>Eq</a> instance.
--   
--   Note that this is a specialized version of <a>permutationsRLE</a>,
--   where each run has been expanded via <a>replicate</a>.
permutations :: MultiSet a -> [[a]]

-- | 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, <tt>permutationsRLE [(<tt>a</tt>,1), (<tt>b</tt>,2)] ==
--   [[(<tt>a</tt>,1),(<tt>b</tt>,2)],[(<tt>b</tt>,2),(<tt>a</tt>,1)],[(<tt>b</tt>,1),(<tt>a</tt>,1),(<tt>b</tt>,1)]]</tt>.
--   
--   (Note that although the output type is equivalent to <tt>[MultiSet
--   a]</tt>, we don't call it that since the output may violate the
--   <a>MultiSet</a> invariant that no element should appear more than
--   once. And indeed, morally this function does not output multisets at
--   all.)
permutationsRLE :: MultiSet a -> [[(a, Count)]]

-- | Element count vector.
type Vec = [Count]

-- | 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.
--   <a>http://www.haskell.org/sitewiki/images/d/dd/TMR-Issue8.pdf</a>
--   
--   See that article for a detailed discussion of the code and how it
--   works.
vPartitions :: Vec -> [MultiSet (Vec)]

-- | 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.
partitions :: MultiSet a -> [MultiSet (MultiSet a)]
instance (Show a) => Show (RMultiSet a)