s c h e m a t i c s : c o o k b o o k

(require (lib "1.ss" "srfi"))

;; Partition : Nat -> (Listof (Listof Number))
(define (partitions n)
   (cond [(= n 0) (list '())]
         [else (fold-right append ()
                           (map (lambda (p)
                                  (if (and (pair? p)
                                           (or (null? (cdr p)) (< (car p) (cadr p))))
                                      (list (cons 1 p) (cons (+ 1 (car p)) (cdr p)))
                                      (list (cons 1 p))))
                                (partitions (- n 1))))]))

> (partitions 0)
(())
> (partitions 1)
((1))
> (partitions 2)
((1 1) (2))
> (partitions 3)
((1 1 1) (1 2) (3))
> (partitions 4)
((1 1 1 1) (1 1 2) (2 2) (1 3) (4))
> (partitions 5)
((1 1 1 1 1) (1 1 1 2) (1 2 2) (1 1 3) (2 3) (1 4) (5))