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


-- | Combinatorial algorithms over multisets
--   
--   Various combinatorial algorithms over multisets, including generating
--   all permutations, partitions, size-2 partitions, size-k subsets,
--   necklaces, and bracelets.
@package multiset-comb
@version 0.2.4.2


-- | Efficient combinatorial algorithms over multisets, including
--   generating all permutations, partitions, subsets, cycles, and other
--   combinatorial structures based on multisets. 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 represented as a list of (element, count) pairs. We
--   maintain the invariants that the counts are always positive, and no
--   element ever appears more than once.
newtype Multiset a
MS :: [(a, Count)] -> Multiset a
[toCounts] :: Multiset a -> [(a, Count)]

-- | A multiset with no values in it.
emptyMS :: Multiset a

-- | Create a multiset with only a single value in it.
singletonMS :: a -> Multiset a

-- | Add an element with multiplicity to a multiset. Precondition: the new
--   element is distinct from all elements already in the multiset.
consMS :: (a, Count) -> Multiset a -> Multiset a

-- | A convenient shorthand for <a>consMS</a>.
(+:) :: (a, Count) -> Multiset a -> Multiset a

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

-- | Efficiently convert a list to a multiset, given an <a>Ord</a> instance
--   for the elements. This method is provided just for convenience. you
--   can also use <a>fromListEq</a> with only an <a>Eq</a> instance, or
--   construct <a>Multiset</a>s directly using <a>fromCounts</a>.
fromList :: Ord a => [a] -> Multiset a

-- | Convert a list to a multiset, given an <a>Eq</a> instance for the
--   elements.
fromListEq :: Eq a => [a] -> Multiset a

-- | Make a multiset with one copy of each element from a list of distinct
--   elements.
fromDistinctList :: [a] -> Multiset a

-- | Construct a <a>Multiset</a> from a list of (element, count) pairs.
--   Precondition: the counts must all be positive, and there must not be
--   any duplicate elements.
fromCounts :: [(a, Count)] -> Multiset a

-- | Extract just the element counts from a multiset, forgetting the
--   elements.
getCounts :: Multiset a -> [Count]

-- | Compute the total size of a multiset.
size :: Multiset a -> Int

-- | Form the disjoint union of two multisets; i.e. we assume the two
--   multisets share no elements in common.
disjUnion :: Multiset a -> Multiset a -> Multiset a

-- | Form the disjoint union of a collection of multisets. We assume that
--   the multisets all have distinct elements.
disjUnions :: [Multiset a] -> Multiset a

-- | List all the distinct permutations of the elements of a multiset.
--   
--   For example, <tt>permutations (fromList "abb") ==
--   ["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 newtype-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)]

-- | Generate all splittings of a multiset into two submultisets, i.e. all
--   size-two partitions.
splits :: Multiset a -> [(Multiset a, Multiset a)]

-- | Generate all size-k submultisets.
kSubsets :: Count -> Multiset a -> [Multiset a]

-- | Generate all distinct cycles, aka necklaces, with elements taken from
--   a multiset. See J. Sawada, "A fast algorithm to generate necklaces
--   with fixed content", J. Theor. Comput. Sci. 301 (2003) pp. 477-489.
--   
--   Given the ordering on the elements of the multiset based on their
--   position in the multiset representation (with "smaller" elements
--   first), in <tt>map reverse (cycles m)</tt>, each generated cycle is
--   lexicographically smallest among all its cyclic shifts, and
--   furthermore, the cycles occur in reverse lexicographic order. (It's
--   simply more convenient/efficient to generate the cycles reversed in
--   this way, and of course we get the same set of cycles either way.)
--   
--   For example, <tt>cycles (fromList "aabbc") ==
--   ["cabba","bcaba","cbaba","bbcaa","bcbaa","cbbaa"]</tt>.
cycles :: Multiset a -> [[a]]

-- | Generate all distinct bracelets (lists considered equivalent up to
--   rotation and reversal) from a given multiset. The generated bracelets
--   are in lexicographic order, and each is lexicographically smallest
--   among its rotations and reversals. See <tt>genFixedBracelets</tt> for
--   a slightly more general routine with references.
--   
--   For example, <tt>bracelets $ fromList "RRRRRRRLLL"</tt> yields
--   
--   <pre>
--   ["LLLRRRRRRR","LLRLRRRRRR","LLRRLRRRRR","LLRRRLRRRR"
--   ,"LRLRLRRRRR","LRLRRLRRRR","LRLRRRLRRR","LRRLRRLRRR"]
--   </pre>
bracelets :: Multiset a -> [[a]]

-- | An optimized bracelet generation algorithm, based on S. Karim et al,
--   "Generating Bracelets with Fixed Content".
--   <a>http://www.cis.uoguelph.ca/~sawada/papers/fix-brace.pdf</a>
--   
--   <tt>genFixedBracelets n content</tt> produces all bracelets (unique up
--   to rotation and reflection) of length <tt>n</tt> using
--   <tt>content</tt>, which consists of a list of pairs where the pair
--   (a,i) indicates that element a may be used up to i times. It is
--   assumed that the elements are drawn from [0..k].
genFixedBracelets :: Int -> [(Int, Int)] -> [Bracelet]

-- | Take a multiset of lists, and select one element from each list in
--   every possible combination to form a list of multisets. We assume that
--   all the list elements are distinct.
sequenceMS :: Multiset [a] -> [Multiset a]
instance GHC.Internal.Base.Functor Math.Combinatorics.Multiset.Multiset
instance Math.Combinatorics.Multiset.Indexable Math.Combinatorics.Multiset.Pre
instance Math.Combinatorics.Multiset.Indexable Math.Combinatorics.Multiset.Pre'
instance Math.Combinatorics.Multiset.Indexable (Math.Combinatorics.Multiset.RLE GHC.Types.Int)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.Combinatorics.Multiset.Multiset a)
instance GHC.Internal.Show.Show Math.Combinatorics.Multiset.Pre
instance GHC.Internal.Show.Show Math.Combinatorics.Multiset.Pre'
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.Combinatorics.Multiset.RLE a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.Combinatorics.Multiset.RMultiset a)
instance Math.Combinatorics.Multiset.Snocable Math.Combinatorics.Multiset.Pre' GHC.Types.Int
instance Math.Combinatorics.Multiset.Snocable Math.Combinatorics.Multiset.Pre GHC.Types.Int
instance GHC.Classes.Eq a => Math.Combinatorics.Multiset.Snocable (Math.Combinatorics.Multiset.RLE a) a
