How to do a powerset in DrRacket?

user_3109171 0
Viewed 10490

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.

htdp powerset racket scheme
5 Answers

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))
user_235670

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) '())
user_51576870
Related