Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to do a powerset in DrRacket?

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.

like image 888
user3109171 Avatar asked Dec 16 '13 23:12

user3109171


People also ask

What is power set method?

Power Set: Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}. If S has n elements in it then P(s) will have 2n elements.

What is power set of a string?

Power Set in Lexicographic order in C++ In this problem, we are given string str. Our task is to print the power set of this string's elements in lexicographical order. Power Set − The power set of a set is the set of all subsets of the set. Denoted by P(S) where s is the set.

What is power set python?

In mathematics, a power set of any set is a set that contains all the possible subsets of a given set along with an empty set. In other words, all subsets of a set is also known as a powerset. There can be a power set of lists, sets, strings, etc., in Python.


1 Answers

            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.
like image 170
Will Ness Avatar answered Nov 03 '22 23:11

Will Ness