(Nils' Scheme Snippets)

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

(combine integer list) => list
(combine* integer list) => list

Purpose

Create combinations of sets. Combine creates combinations without repetition, and combine* creates combinations with repetition. The result is a list of sets (lists).

Arguments

n	size of sets to create
set	source set

Dependencies

id

Example

(combine 2 '(a b c))
=> ((a b) (a c) (b c))
(combine* 2 '(a b c))
=> ((a a) (a b) (a c) (b b) (b c) (c c))

(load "id.scm")

(define (combine4 n set rest base)
  (letrec
    ((limited-map-cdr
       (lambda (set n k)
         (cond ((> n k) '())
           (else (cons set (limited-map-cdr (cdr set)
                                            n
                                            (- k 1)))))))
     (combinations
       (lambda (n set)
         (cond
           ((zero? n) '())
           ((= n 1) (map list set))
           (else (apply
                   append
                   (map (lambda (tail)
                          (map (lambda (sub)
                                 (cons (car tail) sub))
                               (combinations (- n 1) (rest tail))))
                        (limited-map-cdr set
                                         (base n)
                                         (length set)))))))))
    (combinations n set)))

(define (combine n set)
  (combine4 n set cdr id))

(define (combine* n set)
  (combine4 n set id (lambda (x) 1)))

(Nils' Scheme Snippets)

(combine integer list) => list(combine* integer list) => list

(combine integer list) => list
(combine* integer list) => list