;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname 15.supp) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) ;; 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))) (define (arrangements los) (cond [(empty? los) (list empty)] [else (mapcat (lambda (l) (insert-everywhere (first los) l)) (arrangements (rest los)))])) ; mapcat: (A -> (listOf B)) (listOf A) -> (listOf B) ; Purpose: (mapcat f loa) returns the concatenation of the lists (f (first loa)), ..., (f (last loa)) ; Examples (check-expect (mapcat (lambda (e)(list e e)) empty) empty) (check-expect (mapcat (lambda (e)(list e e)) (list 'a)) (list 'a 'a)) (check-expect (mapcat (lambda (e)(list e e)) (list 'a 'b)) (list 'a 'a 'b 'b)) ;Template Instantiation #| (define (mapcat f loa) (cond [(empty? loa) ...] [else ... (first loa) ... (mapcat f (rest loa)) ...])) |# (define (mapcat f loa) (cond [(empty? loa) empty] [else (append (f (first loa)) (mapcat f (rest loa)))])) (check-expect (foldr + 0 empty) 0) (check-expect (foldr + 0 (list 1)) 1) (check-expect (foldr * 1 (list 1 2)) 2) (check-expect (foldr + 0 (list 1 2 3)) 6) ;; 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))) (define (insert-everywhere s los) (cond [(empty? los) (list (list s))] [else (cons (cons s los) (map (lambda (l) (cons (first los) l)) (insert-everywhere s (rest los))))]))