Rearranging Word - Attempt 2

; 1-str is a one-character-string from the set [A-Z] or [a-z]

; Word is either:
; empty
; (cons 1-str Word)

; List-of-word is either:
; (cons Word empty)
; (cons Word (List-of-word))

; word -> list-of word
; returns all possible combinations of word
(define (arrangements w)
  (cond
    [(empty? w) (list empty)]
    [else (insert-everywhere/in-all-words (first w)
            (arrangements (rest w)))]))

; 1str list-of word -> list-of word
; inserts 1-str into all positions of all words in list-of-word
(define (insert-everywhere/in-all-words a-1str a-low)
  (cond
    [(empty? a-low) a-low]
    [else (append (insert-everywhere/in-one-word a-1str (first a-low))
                  (insert-everywhere/in-all-words a-1str (rest a-low)))]))

; 1str word -> list-of word
; inserts 1-str into all positions in word
(define (insert-everywhere/in-one-word a-1str a-word)
  (create-new-words a-1str a-word empty))

; 1-str word word -> list-of-word
; creates new combinations of word
(define (create-new-words l w str-w)
  (cond
    [(empty? w) (list (cons l str-w))]
    [else (cons (create-new-word (move-letters str-w (first w))
                                 l
                                 (rest w))
                (create-new-words l (rest w) (move-letters str-w (first w))))]))

; word 1-str word -> word
; combines two word and 1-str to form new word
(define (create-new-word l1 ins-ltr l2)
  (append l1 (list ins-ltr) l2))

; word 1-str -> word
; appends 1-str to word
(define (move-letters w1 l1)
  (cond
    [(empty? w1) (cons l1 w1)]
    [else (append w1 (list l1))]))