Moved implementations to folder

1 files changed, 69 insertions, 0 deletions

diff --git a/impls/powerset.rkt b/impls/powerset.rkt
new file mode 100644
index 0000000..bbece52
--- /dev/null
+++ b/impls/powerset.rkt
@@ -0,0 +1,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)))))