[Haskell-cafe] Re: Coin changing algorithm

[Ferenc Wagner]

Mark Carroll <markc at chiark.greenend.org.uk> 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.