Partition

Partition.hs

module Partition where

import Data.Function.Memoize

type Target = Int
type Digits = Int
type MaxInt = Int

partitionMaxBrute :: Digits -> Target -> MaxInt -> [[Int]]
partitionMaxBrute d t m
  | d == 0 && t == 0               = [[]]
  | d * m < t || m <= 0            = []
  | t < m                          = partitionMaxBrute d t (t + 1 - d)
  | otherwise                      = partitionMaxBrute d t (m - 1)
                                  ++ fmap (m :) (partitionMaxBrute (d - 1) (t - m) m)

partitionBrute :: Digits -> Target -> [[Int]]
partitionBrute d t = partitionMaxBrute d t (t + 1 - d)

partitionMax :: (Digits -> Target -> MaxInt -> [[Int]]) ->
                 Digits -> Target -> MaxInt -> [[Int]]
partitionMax rec d t m
  | d == 0 && t == 0               = [[]]
  | d * m < t || m <= 0            = []
  | t < m                          = rec d t (t + 1 - d)
  | otherwise                      = rec d t (m - 1)
                                  ++ fmap (m :) (rec (d - 1) (t - m) m)

partition :: Digits -> Target -> [[Int]]
partition d t = memoPM d t (t + 1 - d)
  where memoPM = memoize3 $ partitionMax memoPM