Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <Nobody447095@here-nor-there.org>
Newsgroups: comp.lang.lisp,comp.lang.scheme
Subject: Re: Homework Help! Subsets
Date: Mon, 7 Jul 2025 12:54:47 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 46
Message-ID: <104gg2m$2u48r$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Mon, 07 Jul 2025 14:54:47 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="90eb80e27df105d047d6d87bc8fe395d";
	logging-data="3084571"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19QQgIL8PmXGKGjvRscHPzt"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:cKrhZvsz6VjsLOACdRtJcyappxA=

John Gilson wrote:

> (defun power-set (set)
>     (let ((power-set (list ()))) ; power set always contains empty set
>        (labels
>           ((insert (subset)
>               (loop for elt in set
>                         until (eql elt (first subset))
>                         collect (cons elt subset)))
>            (power-set-length-n (length-m-sets)
>                (mapcan #'(lambda (length-m-set)
>                                    (insert length-m-set))
>                              length-m-sets))
>            (power-set-aux (length-m-sets)
>                ;; n = m + 1
>                (unless (null length-m-sets)
>                   (let ((length-n-sets (power-set-length-n length-m-sets)))
>                      (setf power-set (append length-n-sets power-set))
>                      (power-set-aux length-n-sets)))))
>           (power-set-aux power-set))
>        power-set))
> 
> > (power-set '(1 2 3))
> ((1 2 3) (1 2) (1 3) (2 3) (1) (2) (3) NIL)


Scheme

;; Adapted from a CL version.
(define (powerset List)
  (if (null? List)
    '(())
    (let* ((x (car List))
           (p (powerset (cdr List))))
      (append p
        (map (lambda(xs) (cons x xs)) p)))))

(powerset '(a b c))
  ===>
(() (c) (b) (b c) (a) (a c) (a b) (a b c))


(powerset '(a b c d))
  ===>
(() (d) (c) (c d) (b) (b d) (b c) (b c d) (a) (a d) (a c) (a c d)
 (a b) (a b d) (a b c) (a b c d))