Re: Homework Help! Subsets

John Gilson wrote:

(defun power-set (set)
    (let ((power-set (list ()))) ; power set always contains empty set
       (labels
          ((insert (subset)
              (loop for elt in set
                        until (eql elt (first subset))
                        collect (cons elt subset)))
           (power-set-length-n (length-m-sets)
               (mapcan #'(lambda (length-m-set)
                                   (insert length-m-set))
                             length-m-sets))
           (power-set-aux (length-m-sets)
               ;; n = m + 1
               (unless (null length-m-sets)
                  (let ((length-n-sets (power-set-length-n length-m-sets)))
                     (setf power-set (append length-n-sets power-set))
                     (power-set-aux length-n-sets)))))
          (power-set-aux power-set))
       power-set))
 

(power-set '(1 2 3))

((1 2 3) (1 2) (1 3) (2 3) (1) (2) (3) NIL)

Scheme

;; Adapted from a CL version.
(define (powerset List)
  (if (null? List)
    '(())
    (let* ((x (car List))
           (p (powerset (cdr List))))
      (append p
        (map (lambda(xs) (cons x xs)) p)))))

(powerset '(a b c))
  ===>
(() (c) (b) (b c) (a) (a c) (a b) (a b c))


(powerset '(a b c d))
  ===>
(() (d) (c) (c d) (b) (b d) (b c) (b c d) (a) (a d) (a c) (a c d)
 (a b) (a b d) (a b c) (a b c d))