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) (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 ;;i
 26 12687dd9 2023-08-04 jrmu ;;(cons (cons 'h (cons 'i empty)) empty)
 27 12687dd9 2023-08-04 jrmu ;;hi
 28 12687dd9 2023-08-04 jrmu ;;(cons (cons 'h (cons 'i empty))
 29 12687dd9 2023-08-04 jrmu ;;      (cons (cons 'j (cons 'o (cons 'e empty))) empty)
 30 12687dd9 2023-08-04 jrmu ;;hi joe
 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)))
 33 12687dd9 2023-08-04 jrmu ;;            (cons (cons 'i (cons 't (cons 's empty)))
 34 12687dd9 2023-08-04 jrmu ;;                  empty)))
 35 12687dd9 2023-08-04 jrmu ;;hi joe its
 36 12687dd9 2023-08-04 jrmu ;;(cons (cons 'h (cons 'i empty))
 37 12687dd9 2023-08-04 jrmu ;;      (cons (cons 'j (cons 'o (cons 'e empty)))
 38 12687dd9 2023-08-04 jrmu ;;            (cons (cons 'i (cons 't (cons 's empty)))
 39 12687dd9 2023-08-04 jrmu ;;                  (cons (cons 'm (cons 'e empty)) empty))))
 40 12687dd9 2023-08-04 jrmu ;;hi joe its me
 41 12687dd9 2023-08-04 jrmu ;
 42 12687dd9 2023-08-04 jrmu ;;arrangements : word -> list-of-words
 43 12687dd9 2023-08-04 jrmu ;;Given a-word, return all permutations
 44 12687dd9 2023-08-04 jrmu ;;as a list-of-words.  This is done
 45 12687dd9 2023-08-04 jrmu ;;by inserting the first letter into
 46 12687dd9 2023-08-04 jrmu ;;each permutation of the rest of the word.
 47 12687dd9 2023-08-04 jrmu ;
 48 12687dd9 2023-08-04 jrmu (define (arrangements a-word)
 49 12687dd9 2023-08-04 jrmu   (cond
 50 12687dd9 2023-08-04 jrmu     [(empty? a-word) (cons empty empty)]
 51 12687dd9 2023-08-04 jrmu     [else (insert-everywhere/in-all-words (first a-word)
 52 12687dd9 2023-08-04 jrmu                                           (arrangements (rest a-word)))]))
 53 12687dd9 2023-08-04 jrmu ;
 54 12687dd9 2023-08-04 jrmu ;;insert-everywhere/in-all-words : symbol list-of-words -> list-of-words
 55 12687dd9 2023-08-04 jrmu ;;Given a-symbol and a-low, insert a-symbol into every possible position
 56 12687dd9 2023-08-04 jrmu ;;to generate a new list-of-words.  In general, if the words in a-low
 57 12687dd9 2023-08-04 jrmu ;;contain x letters, there should be (x+1)*x words in the list-of-words output.
 58 12687dd9 2023-08-04 jrmu ;
 59 12687dd9 2023-08-04 jrmu ;
 60 12687dd9 2023-08-04 jrmu ;;Examples
 61 12687dd9 2023-08-04 jrmu ;;(define ex1 (cons empty empty))
 62 12687dd9 2023-08-04 jrmu ;;(insert-everywhere/in-all-words 'a ex1)
 63 12687dd9 2023-08-04 jrmu ;;(cons (cons 'a empty) empty)
 64 12687dd9 2023-08-04 jrmu ;;
 65 12687dd9 2023-08-04 jrmu ;;(define ex2 (cons (cons 'i empty) empty))
 66 12687dd9 2023-08-04 jrmu ;;(insert-everywhere/in-all-words 'a ex2)
 67 12687dd9 2023-08-04 jrmu ;;(cons (cons 'a (cons 'i empty))
 68 12687dd9 2023-08-04 jrmu ;;      (cons (cons 'i (cons 'a empty)) empty))
 69 12687dd9 2023-08-04 jrmu ;;
 70 12687dd9 2023-08-04 jrmu ;;(define ex3 (cons (cons 'h (cons 'i empty))
 71 12687dd9 2023-08-04 jrmu ;;                  (cons (cons 'i (cons 'h empty)) empty)))
 72 12687dd9 2023-08-04 jrmu ;;(insert-everywhere/in-all-words 'b ex3)
 73 12687dd9 2023-08-04 jrmu ;;(cons (cons 'b (cons 'h (cons 'i empty)))
 74 12687dd9 2023-08-04 jrmu ;;      (cons (cons 'h (cons 'b (cons 'i empty)))
 75 12687dd9 2023-08-04 jrmu ;;            (cons (cons 'h (cons 'i (cons 'b empty)))
 76 12687dd9 2023-08-04 jrmu ;;                  (cons (cons 'b (cons 'i (cons 'h empty)))
 77 12687dd9 2023-08-04 jrmu ;;                        (cons (cons 'i (cons 'b (cons 'h empty)))
 78 12687dd9 2023-08-04 jrmu ;;                              (cons (cons 'i (cons 'h (cons 'b empty))) empty))))))
 79 12687dd9 2023-08-04 jrmu ;
 80 12687dd9 2023-08-04 jrmu (define (insert-everywhere/in-all-words a-symbol a-low)
 81 12687dd9 2023-08-04 jrmu  (cond
 82 12687dd9 2023-08-04 jrmu    [(empty? (first a-low))
 83 12687dd9 2023-08-04 jrmu     (insert-symbol-everywhere/in-single-word a-symbol (first a-low) 0)]
 84 12687dd9 2023-08-04 jrmu    [(cons? (first a-low)) ;evaluates true if the first element
 85 12687dd9 2023-08-04 jrmu                           ;in a-low is a word
 86 12687dd9 2023-08-04 jrmu     (cons (insert-everywhere/in-all-words a-symbol (rest a-low))
 87 12687dd9 2023-08-04 jrmu           (insert-symbol-everywhere/in-single-word a-symbol (first a-low) 0))()]))
 88 12687dd9 2023-08-04 jrmu 
 89 12687dd9 2023-08-04 jrmu ;insert-symbol-everywhere/in-single-word : symbol word number -> list-of-words
 90 12687dd9 2023-08-04 jrmu ;Given a-symbol and a-word, inserts a-symbol into every possible position
 91 12687dd9 2023-08-04 jrmu ;to generate a list-of-words. Begins insertion at the nth position.
 92 12687dd9 2023-08-04 jrmu 
 93 12687dd9 2023-08-04 jrmu (define (insert-symbol-everywhere/in-single-word a-symbol a-word n)
 94 12687dd9 2023-08-04 jrmu   (cond
 95 12687dd9 2023-08-04 jrmu     [(empty? a-word) (cons (cons a-symbol empty) empty)]
 96 12687dd9 2023-08-04 jrmu     [(and
 97 12687dd9 2023-08-04 jrmu       (cons? a-word) 
 98 12687dd9 2023-08-04 jrmu       (<= n (length a-word))) 
 99 12687dd9 2023-08-04 jrmu       (cons (insert-symbol-here a-symbol a-word n) 
100 12687dd9 2023-08-04 jrmu             (insert-symbol-everywhere/in-single-word a-symbol a-word (add1 n)))]
101 12687dd9 2023-08-04 jrmu     [(> n (length a-word)) empty]
102 12687dd9 2023-08-04 jrmu     [else (error 'insert-symbol-everywhere/in-single-word "unexpected error")]))
103 12687dd9 2023-08-04 jrmu ;
104 12687dd9 2023-08-04 jrmu ;insert-symbol-here : symbol word number -> word
105 12687dd9 2023-08-04 jrmu ;Given a-symbol and a-word and n, insert a-symbol
106 12687dd9 2023-08-04 jrmu ;in the nth position of a-word.  Right before
107 12687dd9 2023-08-04 jrmu ;the word is the 0th position.  The first position
108 12687dd9 2023-08-04 jrmu ;is right after the first letter.
109 12687dd9 2023-08-04 jrmu ;
110 12687dd9 2023-08-04 jrmu ;Examples:
111 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'a (cons 'n empty) 0)
112 12687dd9 2023-08-04 jrmu ;(cons 'a (cons 'n empty))
113 12687dd9 2023-08-04 jrmu ;
114 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'a (cons 'n empty) 1)
115 12687dd9 2023-08-04 jrmu ;(cons 'n (cons 'a empty))
116 12687dd9 2023-08-04 jrmu ;
117 12687dd9 2023-08-04 jrmu 
118 12687dd9 2023-08-04 jrmu (define (insert-symbol-here a-symbol a-word n)
119 12687dd9 2023-08-04 jrmu   (cond
120 12687dd9 2023-08-04 jrmu     [(= n 0) (cons a-symbol a-word)]
121 12687dd9 2023-08-04 jrmu     [(>= n 1)
122 12687dd9 2023-08-04 jrmu      (cons (first a-word)
123 12687dd9 2023-08-04 jrmu            (insert-symbol-here a-symbol (rest a-word) (sub1 n)))]))
124 12687dd9 2023-08-04 jrmu 
125 12687dd9 2023-08-04 jrmu ;Test insert-symbol-here
126 12687dd9 2023-08-04 jrmu ;(define word1 empty)
127 12687dd9 2023-08-04 jrmu ;(define word2 (cons 'a empty))
128 12687dd9 2023-08-04 jrmu ;(define word3 (cons 'a (cons 'b empty)))
129 12687dd9 2023-08-04 jrmu ;(define word4 (cons 'a (cons 'b (cons 'c empty))))
130 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word1 0)
131 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word2 0)
132 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word2 1)
133 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word3 0)
134 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word3 1)
135 12687dd9 2023-08-04 jrmu ;(insert-symbol-here 'x word3 2)
136 12687dd9 2023-08-04 jrmu 
137 12687dd9 2023-08-04 jrmu ;Examples of insert-symbol-everywhere/in-single-word
138 12687dd9 2023-08-04 jrmu ;
139 12687dd9 2023-08-04 jrmu ;(define ex01 empty)
140 12687dd9 2023-08-04 jrmu ;(insert-symbol-everywhere/in-single-word 'x ex01 0)
141 12687dd9 2023-08-04 jrmu ;(cons (cons 'x empty) empty)
142 12687dd9 2023-08-04 jrmu ;(define ex02 (cons 'a empty))
143 12687dd9 2023-08-04 jrmu ;(insert-symbol-everywhere/in-single-word 'x ex02 0)
144 12687dd9 2023-08-04 jrmu ;(cons (cons 'x (cons 'a empty))
145 12687dd9 2023-08-04 jrmu ;      (cons (cons 'a (cons 'x empty)) empty))
146 12687dd9 2023-08-04 jrmu ;(append (cons (cons 'x (cons 'a empty)) empty)
147 12687dd9 2023-08-04 jrmu ;        (cons (cons 'a (cons 'x empty)) empty))
148 12687dd9 2023-08-04 jrmu ;(define ex03 (cons 'a (cons 'b empty)))
149 12687dd9 2023-08-04 jrmu ;(insert-symbol-everywhere/in-single-word 'x ex03 0)
150 12687dd9 2023-08-04 jrmu ;(cons (cons 'x (cons 'a (cons 'b empty)))
151 12687dd9 2023-08-04 jrmu ;      (cons (cons 'a (cons 'x (cons 'b empty)))
152 12687dd9 2023-08-04 jrmu ;            (cons (cons 'a (cons 'b (cons 'x empty))) empty)))
153 12687dd9 2023-08-04 jrmu ;(define ex04 (list 'p 'a 'r 't 'y))
154 12687dd9 2023-08-04 jrmu ;(insert-symbol-everywhere/in-single-word 'x ex04 0)
155 12687dd9 2023-08-04 jrmu ;
156 12687dd9 2023-08-04 jrmu 
157 12687dd9 2023-08-04 jrmu ;Test insert-everywhere/in-all-words : symbol list-of-words -> list-of-words
158 12687dd9 2023-08-04 jrmu 
159 12687dd9 2023-08-04 jrmu (define ex1 (cons empty empty))
160 12687dd9 2023-08-04 jrmu (insert-everywhere/in-all-words 'a ex1)
161 12687dd9 2023-08-04 jrmu (cons (cons 'a empty) empty)
162 12687dd9 2023-08-04 jrmu 
163 12687dd9 2023-08-04 jrmu (define ex2 (cons (cons 'i empty) empty))
164 12687dd9 2023-08-04 jrmu (insert-everywhere/in-all-words 'a ex2)
165 12687dd9 2023-08-04 jrmu (cons (cons 'a (cons 'i empty))
166 12687dd9 2023-08-04 jrmu       (cons (cons 'i (cons 'a empty)) empty))
167 12687dd9 2023-08-04 jrmu 
168 12687dd9 2023-08-04 jrmu (define ex3 (cons (cons 'h (cons 'i empty))
169 12687dd9 2023-08-04 jrmu                   (cons (cons 'i (cons 'h empty)) empty)))
170 12687dd9 2023-08-04 jrmu (insert-everywhere/in-all-words 'b ex3)
171 12687dd9 2023-08-04 jrmu (cons (cons 'b (cons 'h (cons 'i empty)))
172 12687dd9 2023-08-04 jrmu       (cons (cons 'h (cons 'b (cons 'i empty)))
173 12687dd9 2023-08-04 jrmu             (cons (cons 'h (cons 'i (cons 'b empty)))
174 12687dd9 2023-08-04 jrmu                   (cons (cons 'b (cons 'i (cons 'h empty)))
175 12687dd9 2023-08-04 jrmu                         (cons (cons 'i (cons 'b (cons 'h empty)))
176 12687dd9 2023-08-04 jrmu                               (cons (cons 'i (cons 'h (cons 'b empty))) empty))))))