David Vollbracht

Some time ago Tom, a friend, presented a math programming challenge to a me and a few others. The challenge was to create a function that when given a positive number would return a set of all the sets of positive numbers whose sum was the original number. He wasn’t so much interested in the result itself as he was in what sort of techniques were used in the implementation—memoization of course being a choice candidate for this problem. I was toying a lot with Haskell at the time, and since this was fundamentally a math problem, Haskell seemed well suited to the problem too.

Here’s what I came up with:

  module Decompose
    where

  import Data.List

  decompose = ((map decompose' [0..]) !!) where
    decompose' n = nub (map sort (decompositions n (floor ((toRational n)/2))))

  decompositions n 0 = [[n]]
  decompositions n m = nmCombinations ++ decompositions n (m - 1) where
    nmCombinations = [a ++ b | a <- (decompose (n - m)), b <- (decompose m)]

I was surprised at how short the Haskell solution was. If you run this through Hugs, you’ll see something like this:

  Hugs> :load "Decompose" 
  Decompose> decompose 5
  [[1,1,1,1,1],[1,1,1,2],[1,2,2],[1,1,3],[2,3],[1,4],[5]]
  Decompose> decompose 10
  [[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,2,2],[1,1,1,1,1,1,1,3],[1,1,1,1,1,2,3],[1,1,1,1,1,1,4],[1,1,1,1,1,5],[1,1,1,1,2,2,2],[1,1,1,2,2,3],[1,1,1,1,2,4],[1,1,1,2,5],[1,1,2,2,2,2],[1,2,2,2,3],[1,1,2,2,4],[1,2,2,5],[1,1,1,1,3,3],[1,1,2,3,3],[1,1,1,3,4],[1,1,3,5],[2,2,3,3],[1,2,3,4],[2,3,5],[1,1,4,4],[1,4,5],[5,5],[1,3,3,3],[3,3,4],[2,2,2,2,2],[2,2,2,4],[2,4,4],[1,1,1,1,6],[1,1,2,6],[2,2,6],[1,3,6],[4,6],[1,1,1,7],[1,2,7],[3,7],[1,1,8],[2,8],[1,9],[10]]

The only performance trick in here is indeed memoization, though that may not be obvious at first. It lies in the definition of decompose. The decompose function is really just a list of decomposition results for all positive numbers, indexed by the number being decomposed. Obviously this would be an infinitely long lost, but Haskell has no problem handling that—it just calculates elements of the list on demand. Since decomposing a number always involves decomposing all the numbers below it, the fact that you have to calculate the list out to the length of the original number being decomposed is not a hindrance, it’s actually an advantage!