aboutsummaryrefslogtreecommitdiff
path: root/powerset.rkt
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2023-07-09 22:01:27 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2023-07-09 22:01:27 +0100
commit3592ea3134cbda63d164c158054a6b18ece9ab49 (patch)
tree4f757dcd327b87fe4fcaba7be2149dbb9cac8688 /powerset.rkt
parent13621ae44d1002d30c42afaff055e821969803d7 (diff)
downloadalgorithms-3592ea3134cbda63d164c158054a6b18ece9ab49.tar.gz
algorithms-3592ea3134cbda63d164c158054a6b18ece9ab49.tar.bz2
algorithms-3592ea3134cbda63d164c158054a6b18ece9ab49.zip
(powerset)~Common Lisp -> Racket
Decided to try my hand at racket, fundamentally the algorithm is the same and code structure is basically the same anyway. Just looks cleaner.
Diffstat (limited to 'powerset.rkt')
-rw-r--r--powerset.rkt24
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|