(Nils' Scheme Snippets)

Paren matching: ON | Category: math | Overview | Scheme Books | License

(make-partitions integer) => list

Purpose

Create all partitions of a positive integer. A (number-theoretical) partition of a positive integer n is a set of integers whose sum is equal to n.

Arguments

n	integer to partition

Example

(make-partitions 4)
=> ((4) (3 1) (2 2) (2 1 1) (1 1 1 1))

(define (make-partitions n)
  (letrec
    ((iota
       (lambda (l h)
         (if (= l h)
             (list l)
             (cons l (iota (+ 1 l) h)))))
     (partition
       (lambda (n)
         (cond
           ((zero? n) '(()))
           ((= n 1) '((1)))
           (else (apply append
                        (map (lambda (x)
                               (map (lambda (p)
                                      (cons x p))
                                    (partition (- n x))))
                             (iota 1 n)))))))
     (filter-ascending
       (lambda (p)
         (cond ((null? (cdr p)) p)
           ((apply >= (car p))
             (cons (car p)
                   (filter-ascending (cdr p))))
           (else (filter-ascending (cdr p)))))))
    (reverse (filter-ascending (partition n)))))