partition.scm

(use srfi-1)

; partition(0)
; (null)

; partition(n)
; (n) + part(0)
; (n - 1) + part(1)
; (n - 2) + part(2)
; ...
; (1) + part(n - 1) 

(define (partition-n n)
  (define (iter k)
    (if (= k n)
      '()
      (append
        (map 
          (lambda (tail) (cons (- n k) tail)) 
          (filter (lambda (tail) 
                    (or (null? tail)
                        (<= (car tail) (- n k)))) (partition-n k)))

        (iter (+ k 1)))))
  (if (= n 0)
    (list '())
    (iter 0)))

(partition-n 4)