;; Problem 12.4.2 ;; Contract insert-everywhere/in-all-words: X (listOf (listOf X)) -> (listOf (listOf X)) where X does not overlap (listOf any) ;; Purpose: (insert-everywhere/in-all-words x lox) returns a list of the same type as lox, but replaces each list (e1 ... en) in ;; lox by the collection of lists (x e1 ... en) (e1 x ... en) ... (e1 ... en x). Hence if lox has k elemements, the result has k*(k+1) ;; elements ;; Examples: (check-expect (insert-everywhere/in-all-words 'x empty) empty) ; empty list of lists (check-expect (insert-everywhere/in-all-words 'y (list empty)) (list (list 'y))) ; list containing only the empty list (check-expect (insert-everywhere/in-all-words 'z '((a))) '((z a) (a z))) ; list containing only a singleton list (check-expect (insert-everywhere/in-all-words 'x '((a) (b))) '((x a) (a x) (x b) (b x))) ; list containting two non-empty listsnal example for correctness checking (check-expect (insert-everywhere/in-all-words 'x '((a b) (b a))) '((x a b) (a x b) (a b x) (x b a) (b x a) (b a x))) ;; Template Instantiation #| (define (insert-everywhere/in-all-words x lox) (cond [(empty? lox) ...] [else ... (first los) ... ... (insert-everywhere/in-all-words x (rest lox)) ...])) |# ;; Code (define (insert-everywhere/in-all-words x lox) (cond [(empty? lox) empty] [else (append (insert-everywhere x (first lox)) (insert-everywhere/in-all-words x (rest lox)))])) ;; Contract insert-everywhere: X (listOf X) -> (listOf (listOf X)) ;; Purpose: (insert-everywhere x lox) returns a list of all lists of X values obtaineed from lox by inserting x ;; in a some position within lox. If lox contains k values, (insert-everywhere x lox) contains k+1 lists. ;; Examples: (check-expect (insert-everywhere 'a empty) '((a))) (check-expect (insert-everywhere 'z '(b)) '((z b) (b z))) (check-expect (insert-everywhere 'd '(b c)) '((d b c) (b d c) (b c d))) ;; Tests involving lox input of form (listOf number) instead of (listOf symbol) (check-expect (insert-everywhere 0 '(1 2 3)) '((0 1 2 3) (1 0 2 3) (1 2 0 3) (1 2 3 0))) (check-expect (insert-everywhere 0 '(1 2 3 4)) '((0 1 2 3 4) (1 0 2 3 4) (1 2 0 3 4) (1 2 3 0 4) (1 2 3 4 0))) ;; Template Instantiation #| (define (insert-everywhere x lox) (cond [(empty? lox) ...] [else ... (first lox) ... ... (insert-everywhere x (rest lox)) ...])) |# ;; Code (define (insert-everywhere x lox) (cond [(empty? lox) (list (list x))] [else (cons (cons x lox) (cons-all (first lox) (insert-everywhere x (rest lox))))])) ;; Help functions ;; Contract cons-all: X (listOf (listOf X)) -> (listOf (listOf X)) ;; Purpose: (cons-all o (list l1 ... lk)) returns (list (cons o l1) ... (cons o lk)) ;; Examples: ;; Three essential examples (check-expect (cons-all 0 empty) empty) ; empty list of lists (check-expect (cons-all 0 '(())) '((0))) ; list containing one list (check-expect (cons-all 'a '((b) (c))) '((a b) (a c))) ; list containing more than one list ;; Additional correctness tests (check-expect (cons-all 'a '((b) (c) (d))) '((a b) (a c) (a d))) (check-expect (cons-all 'a '((b c) (d))) '((a b c) (a d))) ;; Template Instantiation #| (define (cons-all x lox) (cond [(empty? lox) ...] [else ... (first lox) ... ... (cons-all x (rest lox))])) |# (define (cons-all x lox) (cond [(empty? lox) empty] [else (cons (cons x (first lox)) (cons-all x (rest lox)))])) ;; NOTE: using functions as data, we can write cons-all more simply as follows: #| (define (cons-all x lox) (map (lambda (e) (cons x e)) lox)) |# ;; Contract arrangements: listOf X -> (listOf (listOf X)) ;; Purpose: (arrangements lox) returns a list of all permutations of lox ;; Examples (check-expect (arrangements empty) (list empty)) (check-expect (arrangements '(a)) '((a))) (check-expect (arrangements '(a b)) '((a b) (b a))) (check-expect (arrangements '(a b c)) '((a b c) (b a c) (b c a) (a c b) (c a b) (c b a))) (check-expect (arrangements '(a b c d)) `((a b c d) (b a c d) (b c a d) (b c d a) (a c b d) (c a b d) (c b a d) (c b d a) (a c d b) (c a d b) (c d a b) (c d b a) (a b d c) (b a d c) (b d a c) (b d c a) (a d b c) (d a b c) (d b a c) (d b c a) (a d c b) (d a c b) (d c a b) (d c b a))) ;; Template Instantiation #| (define (arrangements lox) (cond [(empty? lox) ... ] [else ... (first lox) ... (arrangements (rest lox)) ... ])) |# ;; Code (define (arrangements lox) (cond [(empty? lox) (list empty)] [else (insert-everywhere/in-all-words (first lox) (arrangements (rest lox)))]))