Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
400 views
in Technique[技术] by (71.8m points)

scheme - 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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)
            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.

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...