1 files changed, 24 insertions, 0 deletions
diff --git a/powerset.rkt b/powerset.rkt
new file mode 100644
index 0000000..a746f90
--- /dev/null
+++ b/powerset.rkt
@@ -0,0 +1,24 @@
+#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|