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