#lang racket

(define (subsets-of lst n)
  (cond
    [(null? lst) null] ; 0 ways of making anything out of empty set
    [(= n 0) (list null)] ; 1 way of making a 0 sized subset of something
    [(= n 1) (map list lst)] ; |lst| ways of making singletons
    [else
     (let ([head (car lst)]
           [tail (cdr lst)])
       (append
        ;; HEAD is a part of the subset, so the rest of the subset
        ;; must be an n-1 sized subset of TAIL
        (map (lambda (lst) (cons head lst))
             (subsets-of tail (- n 1)))
        ;; ... or HEAD is not part of the subset, so the subset is
        ;; some n sized subset of TAIL
        (subsets-of tail n)))]))

(define (powerset lst)
  (append* ; flatten list of n sized subsets to just get subsets
   (map (lambda (n)
          (subsets-of lst n)) ; get subset of size n
        (range 0 (+ 1 (length lst)))))) ; n from 0 to |lst|

(define (test? name expected got [equality equal?])
  ;; Print success of test (i.e. (equality expected got)) and return a
  ;; boolean representing if it worked.
  (printf "[TEST ~a]: " name)
  (if (equality expected got)
      (begin
        (displayln "Success")
        #t)
      (begin
        (printf "Failure (expected=~a, got=~a)~n" expected got)
        #f)))

(define-syntax (perform-tests stx)
  (with-syntax
    ([t-clauses
      (datum->syntax
       stx
       (map
        (lambda (clause)
          (syntax-case clause ()
            [(name expected got)
             #'(test? 'name expected got)]))
        (cdr (syntax->list stx))))])
    #'(and (~@ . t-clauses))))

(let ([small (range 10)]
      [medium (range 50)]
      [large (range 100)])
  (perform-tests
   ;; Base case on lst
   ("subsets-of->lst=null->n=0" 0 (length (subsets-of null 0)))
   ("subsets-of->lst=null->n=1024" 0 (length (subsets-of null 1024)))
   ;; Base case on n
   ("subsets-of->lst=[10]->n=0" 1 (length (subsets-of small 0)))
   ("subsets-of->lst=[50]->n=0" 1 (length (subsets-of medium 0)))
   ("subsets-of->lst=[100]->n=0" 1 (length (subsets-of large 0)))
   ;; Singletons
   ("subsets-of->lst=[10]->n=1" 10 (length (subsets-of small 1)))
   ("subsets-of->lst=[50]->n=1" 50 (length (subsets-of medium 1)))
   ("subsets-of->lst=[100]->n=1" 100 (length (subsets-of large 1)))
   ;; Binomial theorem tests (symmetry along the middle of Pascal's triangle)
   ("subsets-of->lst=[10]->n=2~~n=8" (length (subsets-of small 2)) (length (subsets-of small 8)))
   ("subsets-of->lst=[10]->n=3~~n=7" (length (subsets-of small 3)) (length (subsets-of small 7)))
   ("subsets-of->lst=[10]->n=4~~n=6" (length (subsets-of small 4)) (length (subsets-of small 6)))))