úÎ|wã      Safe-Inferred-246+Element count vector.ÂIn order to generate permutations of a multiset, we need to keep 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 information, consisting of a multiset possibly paired with an 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. 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. Precondition: the counts must all be positive, and there must not be any duplicate elements.LExtract just the element counts from a multiset, forgetting the elements.%Compute the total size of a multiset. A multiset with no values in it. 1Create a multiset with only a single value in it. ‹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 b instance 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.RMake a multiset with one copy of each element from a list of distinct elements.jForm the disjoint union of two multisets; i.e. we assume the two multisets share no elements in common.rForm the disjoint union of a collection of multisets. We assume that the multisets all have distinct elements. Convert a  to a  (with no avoided element).  Convert a  to a .DList all the distinct permutations of the elements of a multiset. For example, 7permutations (fromList "abb") == ["abb","bba","bab"] , whereas HData.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 !.ê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 „ 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 elements of a multiset which do not start with the element to avoid (if any).#›Select an element + multiplicity from a multiset in all possible ways, appropriately keeping track of elements to avoid at the start of permutations.$*Componentwise comparison of count vectors.%7'vZero v' produces a zero vector of the same length as v.&Test for the zero vector.'#Do vector arithmetic componentwise.(#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].XGenerate all vector partitions, representing each partition as a multiset of vectors.=This code is a slight generalization of the code published iniBrent Yorgey. "Generating Multiset Partitions". In: The Monad.Reader, Issue 8, September 2007. :http://www.haskell.org/sitewiki/images/d/dd/TMR-Issue8.pdfHSee that article for a detailed discussion of the code and how it works.-/'vHalf v' computes the "lexicographic half" of vª, that is, 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.,c'within m' 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 decreasing list of vectors which are elementwise no greater than m and lexicographically between s and e.í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.]Generate all splittings of a multiset into two submultisets, i.e. all size-two partitions.!Generate all size-k submultisets.Ö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, Qcycles (fromList "aabbc") == ["cabba","bcaba","cbaba","bbcaa","bcbaa","cbbaa"].0]The first parameter is the length of the necklaces being generated. The second parameter p+ is the length of the longest prefix of pre9 which is a Lyndon word, i.e. an aperiodic necklace. preF is the current (reversed) prefix of the necklaces being generated.vAn optimized bracelet generation algorithm, based on S. Karim et al, "Generating Bracelets with Fixed Content". 7http://www.cis.uoguelph.ca/~sawada/papers/fix-brace.pdfgenFixedBracelets n contentL 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].ÿ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 genFixedBracelets8 for a slightly more general routine with references. For example, !bracelets $ fromList "RRRRRRRLLL" yields j["LLLRRRRRRR","LLRLRRRRRR","LLRRLRRRRR","LLRRRLRRRR" ,"LRLRLRRRRR","LRLRRLRRRR","LRLRRRLRRR","LRRLRRLRRR"]´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.O123456789:;<=> ?  "#@$%&'()*+-A,./BC0DEFGHIJKLMNOPQ  G123456789:;<=> ?  "#@$%&'()*+-A,./BC0DEFGHIJKLMNOPQR      ! "#$%&'()*+,-./012345678899::;<=>?@ABCDEFGHIJKLMNOPQRSTUmultiset-comb-0.2.4Math.Combinatorics.MultisetVecMultisetMStoCountsCount fromCounts getCountssizeemptyMS singletonMSconsMS+:toListfromList fromListEqfromDistinctList disjUnion disjUnions permutationspermutationsRLE vPartitions partitionssplitskSubsetscyclesgenFixedBracelets bracelets sequenceMS RMultisetghc-prim GHC.ClassesOrdEqtoRMSfromRMSbaseGHC.List replicatepermutationsRLE' selectRMS<|=vZerovIsZero.+..-.*.vDivvIncwithinvHalfclip withinFromTocycles'BraceletPre'RLEPre PreNecklace Indexable!Snocable|>RMSliftMS expandCountsconsRMSdownFromforaddEltremoveemptyPregetPreemptyRLE compareRLE emptyPre'getPre' uncollate$fSnocablePre'Int$fIndexablePre'$fSnocableRLEa$fIndexableRLE$fIndexablePre$fSnocablePreInt