blob: a746f90c97236ea4dff57a6a4d7dd6a0982defed (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#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|
|
