How to do a powerset in DrRacket?

user3109171 picture user3109171 · Dec 17, 2013 · Viewed 9.4k times · Source

I'm using the beginning language with list abbreviations for DrRacket and want to make a powerset recursively but cannot figure out how to do it. I currently have this much

(define
  (powerset aL)
  (cond
    [(empty? aL) (list)]

any help would be good.

Answer

Will Ness picture Will Ness · Dec 17, 2013
            What's in a powerset? A set's subsets! 
            An empty set is any set's subset,
            so powerset of empty set's not empty. 
            Its (only) element it is an empty set:
(define
  (powerset aL)
  (cond
    [(empty? aL) (list empty)]
    [else
            As for non-empty sets, there is a choice,
            for each set's element, whether to be
            or not to be included in subset
            which is a member of a powerset. 
We thus include
both choices when combining first element with smaller powerset, that, which we get recursively applying the same procedure to the rest of input:
       (combine (first aL)
                (powerset (rest aL)))]))

(define
  (combine a r)                      ; `r` for Recursive Result
  (cond
    [(empty? r)  empty]              ; nothing to combine `a` with
    [else
      (cons (cons a (first r))       ; Both add `a` and
          (cons (first r)            ;   don't add, to first subset in `r`
              (combine               ; and do the same
                    a                ;   with 
                    (rest r))))]))   ;   the rest of `r`
            "There are no answers, only choices". Rather, 
            the choices made, are what the answer's made of.