Finding the subsets of a set

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)
len
(length-iter (cdr a) (+ 1 len))))
(length-iter set 0))

(if (element-of-set? x set)
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) '())
(sub x (trim (helper x))))


migrated from stackoverflow.comOct 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.
• 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.