aboutsummaryrefslogtreecommitdiff
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
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.
-rw-r--r--powerset.lisp25
-rw-r--r--powerset.rkt24
2 files changed, 24 insertions, 25 deletions
diff --git a/powerset.lisp b/powerset.lisp
deleted file mode 100644
index 2a17a07..0000000
--- a/powerset.lisp
+++ /dev/null
@@ -1,25 +0,0 @@
-;;; powerset.lisp --- A program to find the power set of some set
-
-;; Copyright (C) 2021 Aryadev Chavali
-
-;; Author: Aryadev Chavali <aryadev@aryadevchavali.com>
-
-;; This program is free software; you can redistribute it and/or modify
-;; it under the terms of the GNU General Public License as published by
-;; the Free Software Foundation, either version 3 of the License, or
-;; (at your option) any later version.
-
-;; This program is distributed in the hope that it will be useful,
-;; but WITHOUT ANY WARRANTY; without even the implied warranty of
-;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-;; GNU General Public License for more details.
-
-;; You should have received a copy of the GNU General Public License
-;; along with this program. If not, see <https://www.gnu.org/licenses/>.
-
-;;; Commentary:
-;; This program provides a naive counting based approach to finding
-;; specifically sized subsets of some set then using that to generate
-;; the power set. We start by looking for subsets of size n.
-
-;;; Code:
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|