diff options
| -rw-r--r-- | powerset.lisp | 25 | ||||
| -rw-r--r-- | powerset.rkt | 24 |
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| |