[Haskell-beginners] Partition a number or optimize

Mike Meyer mwm at mired.org
Mon Apr 27 16:21:16 UTC 2015


You don't want to do full search here. You want to do a "branch and bound"
search, keeping track of the current best value (which suggests the State
monad) and then terminating searches of subtrees when the best possible
value for that subtree is worse than the current global best possible.

I haven't looked into doing this in Haskell, but it should be a lot faster
than trying to search the full tree.


On Mon, Apr 27, 2015 at 9:23 AM, Animesh Saxena <animeshsaxena at icloud.com>
wrote:

> let cities = 6
> let clinics = 10
> let populations = [1,10000,2,3,400,1]
> let nparts n k = filter ((==n) . sum)  $ replicateM k [1..n]
> let d2 = nparts clinics cities
> let d1 = map maximum (map (\x -> zipWith (/) populations (map (\n->
> fromIntegral n) x)) $ d2)
> maximum $ zipWith (\n x -> (n `div` x) + (n `mod` x) ) populations $ d2 !!
> (head $ filter ((==minimum d1) . (d1 !!)) [0..])
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150427/c79b27c9/attachment.html>


More information about the Beginners mailing list