I am trying to write a procedure that finds the power set of a list, that is, the set of 2n subsets (where n is the number of elements in the list). I simply quite find all the subsets. I feel my code is a lot more work than it should be.

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((not(pair? set)) (display "not a set\n") false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

(define (length set)
  (define (length-iter a len )
    (if (null? a)
        (length-iter (cdr a) (+ 1 len))))
  (length-iter set 0))

(define (adjoin-set x set)
  (if (element-of-set? x set)
      (cons x set)))

(define (conS x w )
  (cond ((null? w) '())
        (else(cons (cons (car x) (cons (car w) '())) (conS x (cdr w))))))

(define (helper s)
  (define (help s newS len)

    (if (<= len 0) newS
        (help (cdr s)(append (adjoin-set s newS) (conS s (cdr s)))(- len 1))))
  (help s '() (length s)))

(define (trim s)
  (let helper((s s) (newS '()) (len (length s)))
    (cond ((<= len 0) newS) 
          ((null?(cdr(car s)))
                 (helper (cdr s) newS(- len 1)))
          (else (helper (cdr s) (adjoin-set (car s) newS) (- len 1))))))

(define (subsets x)
  (define (sub x newSet)
    (if (null? x) newSet
        (sub (cdr x) (adjoin-set (cons (car x) '())
                                 (adjoin-set '() newSet)))))
  (sub x (trim (helper x))))

migrated from stackoverflow.com Oct 15 '14 at 11:21

This question came from our site for professional and enthusiast programmers.


I think in general it's okay, if you need to define all of those yourself (in particular length and element-of-set? that is. trim looks a bit complicated for what it does: If you want to skip single element lists (why?), write it like that, no need for the accumulator and the length call.

The input set should be cleaned up once before the subset generation though, then you won't have to filter the result for duplicates.

  • conS, helper and trim are bad names. The first one is a compatibility issue since you'll find Lisps that are case-insensitive, which will then overwrite the regular cons. Both conS and helper don't say anything at all about what they do. trim essentially the same, a little better maybe. In general, stick with scheme-names-with-dashes-in-between, descriptive names and no camel case.
  • You sometimes skip the space between )_( and add spaces where they don't belong, like _) which looks messy. Indentation is sometimes a bit off, e.g. the if in subsets has the first case on the same line as the if.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.