; powerset

(define (power-set xs)
  (if (null? xs) (list (list))
    (let ((rest (power-set (cdr xs))))
      (append rest (map (lambda (x) (cons (car xs) x)) rest)))))

(display (power-set '(1 2 3))) (newline)

(define (bits n len)
  (let loop ((n n) (len len) (bs (list)))
    (if (zero? len) bs
      (loop (quotient n 2) (- len 1)
            (cons (if (odd? n) 1 0) bs)))))

(define (collect n xs)
  (let loop ((bs (bits n (length xs))) (xs xs) (zs (list)))
    (if (null? bs) zs
      (loop (cdr bs) (cdr xs)
        (if (zero? (car bs)) zs (cons (car xs) zs))))))

(define (power-set xs)
  (do ((n 0 (+ n 1)) (xss (list) (cons (collect n xs) xss)))
      ((= n (expt 2 (length xs))) xss)))

(display (power-set '(1 2 3))) (newline)

(define (for-power-set op xs)
  (let ((len (length xs)))
    (do ((n 0 (+ n 1))) ((= n (expt 2 len)))
      (op (collect n xs)))))

(for-power-set (lambda (s) (display s) (newline)) '(1 2 3))