1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-beginner-reader.ss" "lang")((modname |12.4.1 revised|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp")))))
4 ;Data Definition
5 ;A word is either
6 ;1. an empty list or
7 ;2. (cons l w) where l is a symbol (one of the
8 ;lowercase letters 'a, 'b, ... 'z) and w is a word.
9 ;
10 ;Examples
11 ;empty
12 ;(cons 'i empty)
13 ;(cons 'h (cons 'i empty))
14 ;(cons 'n (cons 'a (cons 'm (cons 'e empty))))
15 ;
16 ;A list-of-words is either
17 ;1. (cons w empty) or
18 ;2. (cons w low) where w is a word
19 ;and low is a list-of-words.
20 ;
21 ;Examples
22 ;(cons empty empty)
23 ;empty empty
24 ;(cons (cons 'i empty) empty)
25 ;(cons (list 'i) empty)
26 ;i
27 ;(cons (cons 'h (cons 'i empty)) empty)
28 ;(cons (list 'h 'i) empty)
29 ;(list (list 'h 'i))
30 ;hi
31 ;(cons (cons 'h (cons 'i empty))
32 ;      (cons (cons 'j (cons 'o (cons 'e empty))) empty))
33 ;(cons (list 'h 'i)
34 ;      (cons (list 'j 'o 'e) empty))
35 ;(list (list 'h 'i)
36 ;      (list 'j 'o 'e))
37 ;hi joe
38 ;(cons (cons 'h (cons 'i empty))
39 ;      (cons (cons 'j (cons 'o (cons 'e empty)))
40 ;            (cons (cons 'i (cons 't (cons 's empty)))
41 ;                  empty)))
42 ;(cons (list 'h 'i)
43 ;      (cons (list 'j 'o 'e)
44 ;            (cons (list 'i 't 's) empty)))
45 ;(list (list 'h 'i)
46 ;      (list 'j 'o 'e)
47 ;      (list 'i 't 's))
48 ;hi joe its
49 ;(cons (cons 'h (cons 'i empty))
50 ;      (cons (cons 'j (cons 'o (cons 'e empty)))
51 ;            (cons (cons 'i (cons 't (cons 's empty)))
52 ;                  (cons (cons 'm (cons 'e empty)) empty))))
53 ;(cons (list 'h 'i)
54 ;      (cons (list 'j 'o 'e)
55 ;            (cons (list 'i 't 's)
56 ;                  (cons (list 'm 'e) empty))))
57 ;(list (list 'h 'i)
58 ;      (list 'j 'o 'e)
59 ;      (list 'i 't 's)
60 ;      (list 'm 'e))
61 ;hi joe its me
62 ;
63 ;arrangements : word -> list-of-words
64 ;Given a-word, return all permutations
65 ;as a list-of-words.  This is done
66 ;by inserting the first letter into
67 ;each permutation of the rest of the word.
68 
69 (define (arrangements a-word)
70   (cond
71     [(empty? a-word) (cons empty empty)]
72     [else (insert-everywhere/in-all-words (first a-word)
73                                           (arrangements (rest a-word)))]))
74 
75 ;insert-everywhere/in-all-words : symbol list-of-words -> list-of-words
76 ;Given a-symbol and a-low, insert a-symbol into every possible position
77 ;to generate a new list-of-words.  In general, if the words in a-low
78 ;contain x letters, there should be (x+1)*x words in the list-of-words output.
79 ;
80 ;
81 ;Examples
82 ;(define ex1 (cons empty empty))
83 ;(insert-everywhere/in-all-words 'a ex1)
84 ;(cons (cons 'a empty) empty)
85 ;
86 ;(define ex2 (cons (list 'i) empty))
87 ;(cons (cons 'i empty) empty)
88 ;(insert-everywhere/in-all-words 'a ex2)
89 ;(cons (cons 'a (cons 'i empty))
90 ;      (cons (cons 'i (cons 'a empty)) empty))
91 ;(cons (list 'a 'i)
92 ;      (cons (list 'i 'a) empty))
93 ;(list (list 'a 'i)
94 ;      (list 'i 'a))
95 ;
96 ;(define ex3 (cons (cons 'h (cons 'i empty))
97 ;                  (cons (cons 'i (cons 'h empty)) empty)))
98 ;(insert-everywhere/in-all-words 'b ex3)
99 ;(cons (cons 'b (cons 'h (cons 'i empty)))
100 ;      (cons (cons 'h (cons 'b (cons 'i empty)))
101 ;            (cons (cons 'h (cons 'i (cons 'b empty)))
102 ;                  (cons (cons 'b (cons 'i (cons 'h empty)))
103 ;                        (cons (cons 'i (cons 'b (cons 'h empty)))
104 ;                              (cons (cons 'i (cons 'h (cons 'b empty))) empty))))))
105 
106 (define (insert-everywhere/in-all-words a-symbol a-low)
107  (cond
108    [(empty? a-low) empty]
109    [(empty? (first a-low))
110     (cons (insert-symbol-everywhere/in-single-word a-symbol (first a-low) 0) empty)]
111    [(cons? (first a-low)) ;evaluates true if the first element
112                           ;in a-low is a word
113     (append (insert-symbol-everywhere/in-single-word a-symbol (first a-low) 0)
114             (insert-everywhere/in-all-words a-symbol (rest a-low)))]))
115 
116 ;insert-symbol-everywhere/in-single-word : symbol word number -> list-of-words
117 ;Given a-symbol and a-word, inserts a-symbol into every possible position
118 ;to generate a list-of-words. Begins insertion at the nth position.
119 
120 (define (insert-symbol-everywhere/in-single-word a-symbol a-word n)
121   (cond
122     [(empty? a-word) (cons a-symbol empty)]
123     [(and
124       (cons? a-word) 
125       (<= n (length a-word))) 
126       (cons (insert-symbol-here a-symbol a-word n) 
127             (insert-symbol-everywhere/in-single-word a-symbol a-word (add1 n)))]
128     [(> n (length a-word)) empty]
129     [else (error 'insert-symbol-everywhere/in-single-word "unexpected error")]))
130 ;
131 ;insert-symbol-here : symbol word number -> word
132 ;Given a-symbol and a-word and n, insert a-symbol
133 ;in the nth position of a-word.  Right before
134 ;the word is the 0th position.  The first position
135 ;is right after the first letter.
136 ;
137 ;Examples:
138 ;(insert-symbol-here 'a (cons 'n empty) 0)
139 ;(cons 'a (cons 'n empty))
140 ;
141 ;(insert-symbol-here 'a (cons 'n empty) 1)
142 ;(cons 'n (cons 'a empty))
143 ;
144 
145 (define (insert-symbol-here a-symbol a-word n)
146   (cond
147     [(= n 0) (cons a-symbol a-word)]
148     [(>= n 1)
149      (cons (first a-word)
150            (insert-symbol-here a-symbol (rest a-word) (sub1 n)))]))
151 
152 ;Test insert-symbol-here
153 ;(define word1 empty)
154 ;(define word2 (cons 'a empty))
155 ;(define word3 (cons 'a (cons 'b empty)))
156 ;(define word4 (cons 'a (cons 'b (cons 'c empty))))
157 ;(insert-symbol-here 'x word1 0)
158 ;(insert-symbol-here 'x word2 0)
159 ;(insert-symbol-here 'x word2 1)
160 ;(insert-symbol-here 'x word3 0)
161 ;(insert-symbol-here 'x word3 1)
162 ;(insert-symbol-here 'x word3 2)
163 
164 ;Examples of insert-symbol-everywhere/in-single-word
165 ;
166 ;(define ex01 empty)
167 ;(insert-symbol-everywhere/in-single-word 'x ex01 0)
168 ;(cons (cons 'x empty) empty)
169 ;(define ex02 (cons 'a empty))
170 ;(insert-symbol-everywhere/in-single-word 'x ex02 0)
171 ;(cons (cons 'x (cons 'a empty))
172 ;      (cons (cons 'a (cons 'x empty)) empty))
173 ;(append (cons (cons 'x (cons 'a empty)) empty)
174 ;        (cons (cons 'a (cons 'x empty)) empty))
175 ;(define ex03 (cons 'a (cons 'b empty)))
176 ;(insert-symbol-everywhere/in-single-word 'x ex03 0)
177 ;(cons (cons 'x (cons 'a (cons 'b empty)))
178 ;      (cons (cons 'a (cons 'x (cons 'b empty)))
179 ;            (cons (cons 'a (cons 'b (cons 'x empty))) empty)))
180 ;(define ex04 (list 'p 'a 'r 't 'y))
181 ;(insert-symbol-everywhere/in-single-word 'x ex04 0)
182 ;
183 
184 ;Test insert-everywhere/in-all-words : symbol list-of-words -> list-of-words
185 ;
186 ;(define ex1 (cons empty empty))
187 ;(insert-everywhere/in-all-words 'a ex1)
188 ;(cons (cons 'a empty) empty)
189 ;
190 ;(define ex2 (cons (cons 'i empty) empty))
191 ;(insert-everywhere/in-all-words 'a ex2)
192 ;(cons (cons 'a (cons 'i empty))
193 ;      (cons (cons 'i (cons 'a empty)) empty))
194 ;
195 ;(define ex3 (cons (cons 'h (cons 'i empty))
196 ;                  (cons (cons 'i (cons 'h empty)) empty)))
197 ;(insert-everywhere/in-all-words 'b ex3)
198 ;(cons (cons 'b (cons 'h (cons 'i empty)))
199 ;      (cons (cons 'h (cons 'b (cons 'i empty)))
200 ;            (cons (cons 'h (cons 'i (cons 'b empty)))
201 ;                  (cons (cons 'b (cons 'i (cons 'h empty)))
202 ;                        (cons (cons 'i (cons 'b (cons 'h empty)))
203 ;                              (cons (cons 'i (cons 'h (cons 'b empty))) empty))))))
204 
205 ;Test insert-everywhere/in-all-words a-symbol a-low
206 ;(define list-a (list (list 'h 'i)
207 ;                     (list 'i 'h)))
208 ;
209 ;(insert-everywhere/in-all-words 'x list-a)
210 ;
211 ;Results
212 ;(list (list 'x 'h 'i)
213 ;      (list 'h 'x 'i)
214 ;      (list 'h 'i 'x)
215 ;      (list 'h 'i 'x)
216 ;      (list 'i 'x' h)
217 ;      (list 'i 'h 'x))
218 
219 (define list2 (list empty))