blob: bbece525a0d73643edbda7effcf85f28f48850d4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#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)
(if (equality expected got)
(begin
(displayln "Success")
#t)
(begin
(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)))))
|
