70 lines
2.6 KiB
Racket
70 lines
2.6 KiB
Racket
#lang racket
|
|
|
|
(define (subsets-of lst n)
|
|
(cond
|
|
[(null? lst) null] ; 0 ways of making anything out of empty set
|
|
[(= n 0) (list null)] ; 1 way of making a 0 sized subset of something
|
|
[(= n 1) (map list lst)] ; |lst| ways of making singletons
|
|
[else
|
|
(let ([head (car lst)]
|
|
[tail (cdr lst)])
|
|
(append
|
|
;; HEAD is a part of the subset, so the rest of the subset
|
|
;; must be an n-1 sized subset of TAIL
|
|
(map (lambda (lst) (cons head lst))
|
|
(subsets-of tail (- n 1)))
|
|
;; ... or HEAD is not part of the subset, so the subset is
|
|
;; some n sized subset of TAIL
|
|
(subsets-of tail n)))]))
|
|
|
|
(define (powerset lst)
|
|
(append* ; flatten list of n sized subsets to just get subsets
|
|
(map (lambda (n)
|
|
(subsets-of lst n)) ; get subset of size n
|
|
(range 0 (+ 1 (length lst)))))) ; n from 0 to |lst|
|
|
|
|
(define (test? name expected got [equality equal?])
|
|
;; Print success of test (i.e. (equality expected got)) and return a
|
|
;; boolean representing if it worked.
|
|
(printf "[TEST ~a]: " name)
|
|
(cond
|
|
[(equality expected got)
|
|
(displayln "Success")
|
|
#t]
|
|
[else
|
|
(printf "Failure (expected=~a, got=~a)~n" expected got)
|
|
#f]))
|
|
|
|
(define-syntax (perform-tests stx)
|
|
(with-syntax
|
|
([t-clauses
|
|
(datum->syntax
|
|
stx
|
|
(map
|
|
(lambda (clause)
|
|
(syntax-case clause ()
|
|
[(name expected got)
|
|
#'(test? 'name expected got)]))
|
|
(cdr (syntax->list stx))))])
|
|
#'(and (~@ . t-clauses))))
|
|
|
|
(let ([small (range 10)]
|
|
[medium (range 50)]
|
|
[large (range 100)])
|
|
(perform-tests
|
|
;; Base case on lst
|
|
("subsets-of->lst=null->n=0" 0 (length (subsets-of null 0)))
|
|
("subsets-of->lst=null->n=1024" 0 (length (subsets-of null 1024)))
|
|
;; Base case on n
|
|
("subsets-of->lst=[10]->n=0" 1 (length (subsets-of small 0)))
|
|
("subsets-of->lst=[50]->n=0" 1 (length (subsets-of medium 0)))
|
|
("subsets-of->lst=[100]->n=0" 1 (length (subsets-of large 0)))
|
|
;; Singletons
|
|
("subsets-of->lst=[10]->n=1" 10 (length (subsets-of small 1)))
|
|
("subsets-of->lst=[50]->n=1" 50 (length (subsets-of medium 1)))
|
|
("subsets-of->lst=[100]->n=1" 100 (length (subsets-of large 1)))
|
|
;; Binomial theorem tests (symmetry along the middle of Pascal's triangle)
|
|
("subsets-of->lst=[10]->n=2~~n=8" (length (subsets-of small 2)) (length (subsets-of small 8)))
|
|
("subsets-of->lst=[10]->n=3~~n=7" (length (subsets-of small 3)) (length (subsets-of small 7)))
|
|
("subsets-of->lst=[10]->n=4~~n=6" (length (subsets-of small 4)) (length (subsets-of small 6)))))
|