-
Notifications
You must be signed in to change notification settings - Fork 1
/
Exercise 2.32 subsets.rkt
executable file
·127 lines (115 loc) · 3 KB
/
Exercise 2.32 subsets.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#lang racket
; Exercise 2.32. 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)))))
; SOLUTION
(define (subsets s)
(if (null? s)
(list null)
(let
((rest (subsets (cdr s))))
(append
rest
(map
(lambda (element)
(cond
((null? (car s)) element)
(else
(cond
((null? element) (list (car s)))
(else
(cons (car s) element)
)
)
)
)
)
rest
)
)
)
)
)
; Explanation: This problem is identical to the count-change problem that appears earlier in
; this book. Let's say that from a given set S, we pick any element e. Then, the elements in
; the set S' of all subsets of S can be segregated into two groups: one whose members contain
; e and the other whose members do not contain e.
; The logic used here is as follows: The set S' of all subsets of a given set S is the union of
; the following two sets:
; 1. The set of all subsets of the set obtained after removing one element, say e from S.
; Let's call this set P.
; 2. The set Q generated from P by adding e to each element in P
; The 'map' function above does exactly what is described in step 2 above. The variable 'rest'
; is the same as set P above.
; S' = P union Q
; Note: The procedure above works well even when the set elements are lists/pairs themselves
; Tests
Welcome to DrRacket, version 6.11 [3m].
Language: racket, with debugging; memory limit: 128 MB.
> (subsets null)
'(())
> (subsets (list 1))
'(() (1))
> (subsets (list 1 2))
'(() (2) (1) (1 2))
> (subsets (list 1 2 3))
'(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
> (subsets (list 1 2 3 4))
'(()
(4)
(3)
(3 4)
(2)
(2 4)
(2 3)
(2 3 4)
(1)
(1 4)
(1 3)
(1 3 4)
(1 2)
(1 2 4)
(1 2 3)
(1 2 3 4))
> (subsets (subsets null))
'(() ())
> (subsets (subsets (list 1)))
'(() ((1)) () ((1)))
> (define lol (list (list 1 2) (list 3 4) 5))
> lol
'((1 2) (3 4) 5)
> (subsets lol)
'(() (5) ((3 4)) ((3 4) 5) ((1 2)) ((1 2) 5) ((1 2) (3 4)) ((1 2) (3 4) 5))
> (define clol (list (list 1 2) 3))
> clol
'((1 2) 3)
> (subsets clol)
'(() (3) ((1 2)) ((1 2) 3))
> (define nlist (list 1 (list 2) (list 3 (list 4)) (list (list 5))))
> nlist
'(1 (2) (3 (4)) ((5)))
> (subsets nlist)
'(()
(((5)))
((3 (4)))
((3 (4)) ((5)))
((2))
((2) ((5)))
((2) (3 (4)))
((2) (3 (4)) ((5)))
(1)
(1 ((5)))
(1 (3 (4)))
(1 (3 (4)) ((5)))
(1 (2))
(1 (2) ((5)))
(1 (2) (3 (4)))
(1 (2) (3 (4)) ((5))))
>