-- | Partitions of a multiset
module Math.Combinat.Partitions.Multiset where

--------------------------------------------------------------------------------

import Data.Array.Unboxed
import Data.List

import Math.Combinat.Partitions.Vector

--------------------------------------------------------------------------------
                              
-- | Partitions of a multiset. Internally, this uses the vector partition algorithm
partitionMultiset :: (Eq a, Ord a) => [a] -> [[[a]]]
partitionMultiset :: forall a. (Eq a, Ord a) => [a] -> [[[a]]]
partitionMultiset [a]
xs = [[[a]]]
parts where
  parts :: [[[a]]]
parts = (forall a b. (a -> b) -> [a] -> [b]
map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map) ([Int] -> [a]
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (a :: * -> * -> *) e i. (IArray a e, Ix i) => a i e -> [e]
elems) [[UArray Int Int]]
temp
  f :: [Int] -> [a]
f [Int]
ns = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Int -> a -> [a]
replicate [Int]
ns [a]
zs)
  temp :: [[UArray Int Int]]
temp = [Int] -> [[UArray Int Int]]
fasc3B_algorithm_M [Int]
counts
  counts :: [Int]
counts = forall a b. (a -> b) -> [a] -> [b]
map forall (t :: * -> *) a. Foldable t => t a -> Int
length [[a]]
ys
  ys :: [[a]]
ys = forall a. Eq a => [a] -> [[a]]
group (forall a. Ord a => [a] -> [a]
sort [a]
xs) 
  zs :: [a]
zs = forall a b. (a -> b) -> [a] -> [b]
map forall a. [a] -> a
head [[a]]
ys

--------------------------------------------------------------------------------