Here’s a draft of the article I’m writing for hopeful inclusion in the upcoming issue of The Monad.Reader:
[EDIT, 11/10/2007: I've removed the draft version since it seems that people are finding it from searches and reading it without realizing it's a draft. I'd much rather people read the (much better) version that was actually published in the Monad.Reader: you can find it here, in Issue #8 of the Monad.Reader. The literate Haskell source can be found here.]
I’d be extremely grateful to anyone who felt inclined to read it and offer comments (it’s about 12 pages). I’m particularly interested in whether it is (in your opinion) clear, and whether it is written at an appropriate level, or if it could use more/less explanation; but of course I’d be grateful for feedback of any sort. I’m also curious whether anyone can point to anything related in the literature. I haven’t turned anything up but I can’t imagine this has never been done before.
To give a very brief synopsis, the article starts out with the problem of efficiently enumerating all the partitions of a multiset — for example, [1,1,2] has four unique partitions: [[[1,1,2]], [[1,1],[2]], [[1,2], [1]], [[1],[1],[2]]]. I then develop some Haskell code to enumerate vector partitions, and use this to compute multiset partitions by representing multisets as vectors of element counts. That’s the bare-bones outline, although there’s more to it than that, of course — in particular the vector partition code ends up having a few additional applications as well. I think it’s neat and (mostly) pretty elegant.
So, thanks in advance to anyone who takes the time to offer me some feedback! Maybe someday I’ll get a chance to bake you some cookies. Or something.
I think Knuth has considered multiset partitions.
You could also check out the work by Wilf
http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html
http://www.math.upenn.edu/~wilf/lecnotes.html
http://www.math.upenn.edu/~wilf/
For a list of books see
http://cs.uiowa.edu/~sriram/196/fall01/syllabus.html
Great article. As you say, realising that multisets are isomorphic to vectors in N^n is key. Incidentally, did you realise that this means that they are also isomorphic to monomials. For example, [1,2,3,3,3] would be x1x2x3^3 (or xyz^3).
I think that it’s possible that some of the code can be written more concisely (though perhaps less efficiently). Given a vector v <- N^n, the following seems to be able to find all descending ordered lists of vectors which sum to v:
vecDivisors (n:ns) = [i:is | i <- [0..n], is <- vecDivisors ns]
vecDivisors [] = [[]]
vecPartitions vec = let ds = reverse $ tail $ vecDivisors vec in vecPartitions’ ds (head ds) where
vecPartitions’ [] r = if all (==0) r then [[]] else []
vecPartitions’ (v:vs) r = if v <|= r
then map (v:) (vecPartitions’ (v:vs) (r .- v)) ++ vecPartitions’ vs r
else vecPartitions’ vs r
(It’s a generalisation of the partitions function at http://www.polyomino.f2s.com/david/haskell/hs/CombinatoricsGeneration.hs.txt)
@Jan: Thanks for the links. I just (yesterday) acquired Volume 4, Fascicle 3 of TAOCP and Knuth does indeed cover multiset partitions. I didn’t see anything in Wilf’s book that you linked to, but I’ll keep looking around a bit. Thanks for the links!
@David: It did occur to me that they are also isomorphic to monomials, but forgot to mention it in the article. Thanks for the reminder! Thanks for the code as well; some informal benchmarks indicate that it’s somewhat (~3x-4x) slower than mine, but it certainly is more concise. Hopefully in the next couple days I can sit down to think about it in depth and see whether there are any improvements I can make based on it.