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