úÎi'f¢     .Element count vector. AIn order to generate permutations of a multiset, we need to keep D track of the most recently used element in the permutation being  built, so that we don'!t use it again immediately. The   type (for "restricted multiset") records this A information, consisting of a multiset possibly paired with an C element (with multiplicity) which is also part of the multiset, < but should not be used at the beginning of permutations. ?A multiset is represented as a list of (element, count) pairs. C We maintain the invariants that the counts are always positive, / and no element ever appears more than once.  Construct a ( from a list of (element, count) pairs. E Precondition: the counts must all be positive, and there must not  be any duplicate elements. @Extract just the element counts from a multiset, forgetting the  elements. ?Add an element with multiplicity to a multiset. Precondition: @ the new element is distinct from all elements already in the  multiset. A convenient shorthand for . Convert a multiset to a list.  3Efficiently convert a list to a multiset, given an  instance D for the elements. This method is provided just for convenience.  you can also use   with only an  instance, or  construct s directly using . 'Convert a list to a multiset, given an  instance for the  elements. =Make a multiset with one copy of each element from a list of  distinct elements. AForm the disjoint union of two multisets; i.e. we assume the two * multisets share no elements in common. AForm the disjoint union of a collection of multisets. We assume 2 that the multisets all have distinct elements.  Convert a  to a  (with no avoided element).  Convert a  to a . 8List 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  instance. +Note that this is a specialized version of , ( where each run has been expanded via . BList all the distinct permutations of the elements of a multiset, < with each permutation run-length encoded. (Note that the E 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 ) invariant that no element should appear ? more than once. And indeed, morally this function does not  output multisets at all.) ?List all the (run-length encoded) distinct permutations of the A elements of a multiset which do not start with the element to  avoid (if any). !ASelect an element + multiplicity from a multiset in all possible A ways, appropriately keeping track of elements to avoid at the  start of permutations. "#+Componentwise comparison of count vectors. $'vZero v'. produces a zero vector of the same length as v. %Test for the zero vector. &'$Do vector arithmetic componentwise. (%Multiply a count vector by a scalar. )'v1 ) v2'# is the largest scalar multiple of v2 which is % elementwise less than or equal to v1. *' vInc within v' lexicographically increments v with respect to  +. For example,  vInc [2,3,5] [1,3,4] == [1,3,5], and   vInc [2,3,5] [1,3,5] == [2,0,0]. AGenerate 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 ISee that article for a detailed discussion of the code and how it works. ,'vHalf v' computes the "lexicographic half" of v , that is, C the vector which is the middle element (biased towards the end) = in a lexicographically decreasing list of all the vectors  elementwise no greater than v. +'within m'2 generates a lexicographically decreasing list of ' vectors elementwise no greater than m. -!Clip one vector against another. .'withinFromTo m s e'+ efficiently generates a lexicographically D decreasing list of vectors which are elementwise no greater than  m and lexicographically between s and e. BEfficiently generate all distinct multiset partitions. Note that A each partition is represented as a multiset of parts (each of C which is a multiset) in order to properly reflect the fact that ( some parts may occur multiple times. =Generate all splittings of a multiset into two submultisets, ! i.e. all size-two partitions. "Generate all size-k submultisets. AGenerate 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. BGiven the ordering on the elements of the multiset based on their 1 position in the multiset representation (with "smaller"  elements first), in map reverse (cycles m), each generated D 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 E 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"]. /9The first parameter is the length of the necklaces being $ generated. The second parameter p is the length of the longest  prefix of pre+ which is a Lyndon word, i.e. an aperiodic  necklace. pre) is the current (reversed) prefix of the  necklaces being generated. @Take a multiset of lists, and select one element from each list B in every possible combination to form a list of multisets. We 3 assume that all the list elements are distinct. 0    1      !"#$%&'()*+,-./0123456multiset-comb-0.2Math.Combinatorics.MultisetVecMultisetMStoCountsCount fromCounts getCountsconsMS+:toListfromList fromListEqfromDistinctList disjUnion disjUnions permutationspermutationsRLE vPartitions partitionssplitskSubsetscycles sequenceMS RMultisetRMSliftMS expandCountsbase GHC.ClassesOrdEqtoRMSfromRMSGHC.List replicatepermutationsRLE' selectRMSconsRMS<|=vZerovIsZero.+..-.*.vDivvIncwithinvHalfclip withinFromTocycles' uncollate