[plt-scheme] On continuations...

Matthias Felleisen wrote:

> ;; Partition : comment .scheme with #; and delete #; from python to 
> switch
> ;; Nat -> (Listof (Listof Number))
> (define (partitions.scheme n)
>   (cond [(= n 0) (list empty)]
>         [else (foldr 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))))]))
>

The following is a straightforward port Skiena's implementation
of Partitions in the Combinatorica package of Mathematica.

; table : object integer -> (list object)
;   return a list consisting of n copies of the object o
(define (table o n)
  (cond
    [(= n 0) '()]
    [else    (cons o (table o (- n 1)))]))

; partitions : integer -> (list integer)
;   return a list of the partions of the integer n
(define (partitions n)
  ; parts : integer integer -> (list integer)
  ;   return a list of all partitions of n, where all addends are m or 
smaller.
  ;   E.g. (parts 6 2) = ((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))
  (define (parts n m)
    (cond
      [(< n 0) '()]
      [(= n 0) '(())]
      [(= m 1) (list (table 1 n))]
      [(= m 0) '()]
      [else    (append (map (lambda (l) (cons m l))
                            (parts (- n m) m))
                       (parts n (- m 1)))]))
  (parts n n))

;;; Test

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

;;; Output

(())
((1))
((2) (1 1))
((3) (2 1) (1 1 1))
((4) (3 1) (2 2) (2 1 1) (1 1 1 1))
((5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))
((6) (5 1) (4 2) (4 1 1) (3 3) (3 2 1) (3 1 1 1) (2 2 2) (2 2 1 1) (2 1 
1 1 1) (1 1 1 1 1 1))

;;; Other examples

 > (parts 6 3)
((3 3) (3 2 1) (3 1 1 1) (2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))
 > (parts 6 2)
((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))
 > (parts 6 0)
()
 > (parts 6 1)
((1 1 1 1 1 1))

-- 
Jens Axel Søgaard