[plt-scheme] On continuations...

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Sun Dec 19 18:27:46 EST 2004 Previous message: [plt-scheme] On continuations... Next message: [plt-scheme] On continuations... Messages sorted by: [date] [thread] [subject] [author]

```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)
>                                 (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

```

 Posted on the users mailing list. Previous message: [plt-scheme] On continuations... Next message: [plt-scheme] On continuations... Messages sorted by: [date] [thread] [subject] [author]