-- 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 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.
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 consMS.
(+:) :: (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 Ord instance
--   for the elements. This method is provided just for convenience. you
--   can also use fromListEq with only an Eq instance, or
--   construct Multisets directly using fromCounts.
fromList :: Ord a => [a] -> Multiset a

-- | Convert a list to a multiset, given an Eq 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 Multiset 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, permutations (fromList "abb") ==
--   ["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.
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, 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 newtype-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.)
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.
--   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.
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 map reverse (cycles m), 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, cycles (fromList "aabbc") ==
--   ["cabba","bcaba","cbaba","bbcaa","bcbaa","cbbaa"].
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 genFixedBracelets for
--   a slightly more general routine with references.
--   
--   For example, bracelets $ fromList "RRRRRRRLLL" yields
--   
--   
--   ["LLLRRRRRRR","LLRLRRRRRR","LLRRLRRRRR","LLRRRLRRRR"
--   ,"LRLRLRRRRR","LRLRRLRRRR","LRLRRRLRRR","LRRLRRLRRR"]
--   
bracelets :: Multiset a -> [[a]]

-- | An optimized bracelet generation algorithm, based on S. Karim et al,
--   "Generating Bracelets with Fixed Content".
--   http://www.cis.uoguelph.ca/~sawada/papers/fix-brace.pdf
--   
--   genFixedBracelets n content produces all bracelets (unique up
--   to rotation and reflection) of length n using
--   content, 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
