[plt-scheme] Re: On continuations...

Sure, if you accept accumulator-style. -- Matthias


On Dec 19, 2004, at 8:06 PM, karczma at info.unicaen.fr wrote:

>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> Matthias Felleisen writes:
>> P.S. If you come across a specification of the mathematical solution 
>> in math, could you please share with us? Most mathematicians dont 
>> really use higher-order functions much so there solution is typically 
>> much longer and I'd love to see what they do instead.
>
> Well, I present my solution, which seems slightly simpler than what
> has been proposed by Jens Axel Søgaard.
> The mathematical idea is not so mathematical after all, rather 
> structural.
> Map is useful, and fold *may* be used, but the straight recursion is
> simpler. No tables needed.
> Take *one* concrete partition of 10, say the Ferrer diagram (or, as
> physicists say, an (unfilled) Young diagram): (6,2,1,1)
> ******
> **
> *
> *
> It should be obvious that all partitions of N are: (N), and all 
> partitions
> (pkmax n (n-1)), where (pkmax n k) are all partitions restricted so 
> that the
> longest segment is equal or shorter than k.
> Now, pkmax can be decomposed into two contributions. First, with the 
> longest
> segment really equal to k, and
> all lower restricted partitions, i.e., pkmax n (k-1).
> Here you are the program in Haskell
> part n | n>0 = [n] : pkmax n (n-1)
>      | otherwise = []
> pkmax n k | n>0 && k>0 = map (k:) (pkmax (n-k) k) ++ pkmax n (k-1)
>         | n==0 = [[]]
>         | otherwise = []
> and its translation into Scheme:
> (define (part n)
> (if (> n 0) (cons (list n) (pkmax n (- n 1)))
>     ()))
> (define (pkmax n k)
> (cond ((and (> n 0) (> k 0))
>        (append (map (lambda (x) (cons k x))
>                     (pkmax (- n k) k))
>                (pkmax n (- k 1))) )
>       ((= n 0) (list ()))
>       (else ())))
> =================================
> Jerzy Karczmarczuk
>