[Haskell-cafe] Re: Coin changing algorithm

Mark Carroll writes:

On Wed, 13 Jul 2005, Dinh Tien Tuan Anh wrote:

(snip)

...

eg: m = 75, k = 5 => [50, 20, 5] [50, 20, 1,2,2] (snip) Is this problem suitable for functional programming language ?

Oh, what fun. I like this sort of thing. My quick attempt is:

Just for more fun, here is my solution for all the partitions of all Ints. Yes, I really used it for real work (quantum field theory, heh). There is no limit on the lengths, but that could be easily added, I think. And it's fully memoized. Here we go:

partitions :: [[[Int]]] partitions = [[]]:[[n]:concat [map (m:) $ dropWhile ((m<).head) pars | (m,pars) <- zip [n-1,n-2..1] (tail partitions)] | n <- [1..]] -- Feri.