úÎC A… 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. AA multiset is a list of (element, count) pairs. We maintain the B invariants that the counts are always positive, and no element  ever appears more than once. Convert a multiset to a list. @Convert a list to a multiset. This method is provided just for 5 convenience; you can of course construct your own s > directly (especially if the type of the elements is not an  instance of  ).  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 [(a,1), (b,2)] ==  ["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)]]. 5(Note that although the output type is equivalent to  [MultiSet  a], we don'0t call it that since the output may violate the  3 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 E 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.          !"#$multiset-comb-0.1Math.Combinatorics.MultisetVecMultiSetCounttoListfromList permutationspermutationsRLE vPartitions partitions RMultiSetRMSbase GHC.ClassesOrdtoRMSfromRMSEqGHC.List replicatepermutationsRLE' selectRMSconsRMS<|=vZerovIsZero.+..-.*.vDivvIncwithinvHalfclip withinFromTo