[plt-scheme] Permutation correct way to do it ?

From: richard gere (diggerrrrr at gmail.com)
Date: Thu Apr 3 07:56:28 EDT 2008

After struggling for hours , finally i was able to solve the excercise 12.4.2 .

I want to know , if this is the correct approach , and does my
solution reflects what the author of the exercise had in its mind ?
Here is my code :


;;A word is either
;;1. empty or
;;2. (cons a wd) where a is a symbol in 'a,'b,'c,...'z and wd is a word
;;eg (cons 'b empty) is a word , and
;; (cons 'r (cons 'e (cons 'a (cons 'd empty) ))) is a word

;;A list-of-words is either
;;1. empty or
;;2 (cons wd lw) where wd is a word and lw is a list-of-words
;;(cons (cons 'r (cons 'e (cons 'a (cons 'd empty))))
;;      (cons (cons 'd (cons 'e (cons 'a (cons 'r empty)))) empty))

;;length1 : word -> number
;;to compute the length of a-word or for any list
(define (length1 a-word)
    [(empty? a-word) 0]
    [ else (+ 1 (length1 (rest a-word)))]))

;;(length1 (cons 'a (cons 'b empty)))

;;insert-at : number symbol word -> word
;;to insert a-sym at pos i in a-word
(define (insert-at i a-sym a-word)

    [(zero? i) (cons a-sym  a-word) ]
    [(empty? a-word) empty]
    [else (cons (first a-word) (insert-at (sub1 i) a-sym (rest a-word)))]))

;;(insert-at 1 'z (cons 'a (cons 'b empty)))
;;(insert-at 0 'z (cons 'a (cons 'b empty)))

;;for-all-pos: number word symbol : list-of-words
;;to create a list of words by inserting a-sym in a-word at all
positions i.e 0..n
;;each forming a word
(define (for-all-pos n a-word a-sym)
    [(zero? n) (cons (cons a-sym a-word) empty) ]
    [else (cons (insert-at n a-sym a-word) (for-all-pos (sub1 n)
a-word a-sym))]))

;;(define A-WORD (cons 'a (cons 'b empty)))
;;(for-all-pos (length1 A-WORD) A-WORD 'z)

;;insert-everywhere/in-all-words : symbol list-of-words -> list-of-words
;;to create a list-of-words by inserting a-sym everywhere in word for all word
;;in alow
(define (insert-everywhere/in-all-words a-sym alow)
    [(empty? alow) empty ]
    [else (append (for-all-pos (length1 (first alow)) (first alow) a-sym)
          (insert-everywhere/in-all-words a-sym (rest alow))) ]))
;;(insert-everywhere/in-all-words 'z (cons (cons 'a (cons 'b empty))
(cons (cons 'b (cons 'a empty)) empty)))

;;arrangements : word -> list-of-words
;;to create a list of all re-arrangement of letters in a-word
(define (arrangements a-word)
    [(empty? a-word) (cons empty empty)]
    [else (insert-everywhere/in-all-words (first a-word)
                                         (arrangements (rest a-word)))]))

;;(arrangements (cons 'd (cons 'e (cons 'r empty) )))

;;(length1 (arrangements (cons 'd (cons 'e (cons 'r empty) ))))
;;(length1 (arrangements (cons 'd (cons 'e (cons 'r (cons 'a empty) ) ))))

;;Hurray !!!



Posted on the users mailing list.