# [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
*>*
*