Draft of my TMR article on multiset partitions

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.

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in haskell, writing. Bookmark the permalink.

3 Responses to Draft of my TMR article on multiset partitions

  1. DavidA says:

    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)

  2. Brent says:

    @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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.