SICP subsets exercise in python?

[Brian Zhou]

Just curious if I can do it easily in Python, kind of give up after a few
tries. Anyone?

/Brian


Exercise. We can represent a set as a list of distinct elements, and we can
represent the set of all subsets of the set as a list of lists. For example,
if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1)
(1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that
generates the set of subsets of a set and give a clear explanation of why it
works:
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map ?? rest)))))

Scheme:

(define (subsets s)
  (if (null? s)
    '(())
    (let ((rest (subsets (cdr s))))
      (append rest (map (lambda (ss) (cons (car s) ss)) rest)))))

Haskell:

subsets []      = [[]]
subsets (x:xs)  = let rest = subsets xs
                   in rest ++ (map (x:) rest)