-- 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, and -- Sawada's algorithm for generating all necklaces with elements from a -- multiset. @package multiset-comb @version 0.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)] -- | 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] -- | 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]] -- | 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 (Show a) => Show (RMultiset a) instance (Show a) => Show (Multiset a) instance Functor Multiset