How to do a powerset in DrRacket?

Question

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.

Hackberry

rosettacode.org/wiki/Power_set#Racket – Heine

(require racket/list) (define powerset combinations) docs.racket-lang.org/reference/… – Patroclus

Answer 1

            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.

Siclari

Answer 2

In Racket,

#lang racket

(define (power-set xs)
  (cond
    [(empty? xs) (list empty)]                 ; the empty set has only empty as subset
    [(cons? xs)  (define x  (first xs))        ; a constructed list has a first element
                 (define ys (rest  xs))        ; and a list of the remaining elements
                 ;; There are two types of subsets of xs, thouse that
                 ;; contain x and those without x.
                 (define with-out-x            ; the power sets without x
                   (power-set ys))                 
                 (define with-x                ; to get the power sets with x we 
                   (cons-all x with-out-x))    ; we add x to the power sets without x
                 (append with-out-x with-x)])) ; Now both kind of subsets are returned.

(define (cons-all x xss)
  ; xss is a list of lists
  ; cons x onto all the lists in xss
  (cond
    [(empty? xss) empty]
    [(cons?  xss) (cons (cons     x (first xss))    ; cons x to the first sublist
                        (cons-all x (rest xss)))])) ; and to the rest of the sublists

To test:

(power-set '(a b c))

Arun

Answer 3

Here's yet another implementation, after a couple of tests it appears to be faster than Chris' answer for larger lists. It was tested using standard Racket:

(define (powerset aL)
  (if (empty? aL)
      '(())
      (let ((rst (powerset (rest aL))))
        (append (map (lambda (x) (cons (first aL) x))
                     rst)
                rst))))

Diluvium

Yep, that was the original implementation I wrote (since it's more straightforward than the version I eventually posted, and was thus what intuitively came to mind), but I didn't like the order of the resulting elements. (I know, since when are sets about ordering, right?) Still, have a +1. :-) – Taub

Answer 4

Here's my implementation of power set (though I only tested it using standard Racket language, not Beginning Student):

(define (powerset lst)
  (if (null? lst)
      '(())
      (append-map (lambda (x)
                    (list x (cons (car lst) x)))
                  (powerset (cdr lst)))))

(Thanks to samth for reminding me that flatmap is called append-map in Racket!)

Taub

I like this solution, it's simpler than the one I posted, and a good example showing the usage of append-map. I wonder, why is it slower? – Acatalectic

Answer 5

You can just use side effect:

(define res '())

(define
  (pow raw leaf)
  (cond
    [(empty? raw) (set! res (cons leaf res))
                  res]
    [else (pow (cdr raw) leaf)
          (pow (cdr raw) (cons (car raw) leaf))]))

(pow '(1 2 3) '())

Lattermost

there's no set! in docs.racket-lang.org/htdp-langs/…, though. but nice and simple recursive-backtracking, this. – Siclari

It can run on DrRacket. – Lattermost

the question says "I'm using the beginning language with list abbreviations". and I upvoted. :) – Siclari

OK, thank you for the correction. I had also upvoted yours. – Lattermost