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

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Thu Apr 3 18:03:48 EDT 2008

Now that I am actually not in a meeting, I see that your code does  
not follow the design recipe at all. This exercise is within reach  
for someone who has never programmed before and follows the recipe;  
if you fall in this group, systematically use the recipe and you will  
get there. It is a stumbling block for people who have programmed  
before and believe that I made up the design recipe to torture them.  
(This is my class room experience.)

I encourage you to study up on the design recipe and to apply it  
rigorously to every function needed for this exercise.

-- Matthias





On Apr 3, 2008, at 11:08 AM, richard gere wrote:
> Thanks for your kind reply.
> I did not got the expected result for :
>
>  (check-expect (arrangements '(a t))
>                  '((a t) (t a)))
>
> so i have now re-defined/changed  "for-all-pos" and
> "insert-everywhere/in-all-words"  functions .
> Here are the new definitions :
>
>
> (define (for-all-pos n a-word a-sym)
>   (cond
>     [(= n (length1 a-word)) (cons (insert-at n a-sym a-word) empty) ]
>     ;;[(zero? n) (cons (insert-at n a-sym a-word) empty) ]
>
>     [else (cons (insert-at n a-sym a-word) (for-all-pos (add1 n)
> a-word a-sym))]))
>
>
>
>
> (define (insert-everywhere/in-all-words a-sym alow)
>   (cond
>     [(empty? alow) empty ]
>     [else (append (for-all-pos 0 (first alow) a-sym)
>           (insert-everywhere/in-all-words a-sym (rest alow))) ]))
>
>
> Tested them with two different data set and  both were successful :
>
> (check-expect (arrangements (cons 'a (cons 't empty))) (cons (cons 'a
> (cons 't empty))
>                                                              (cons
> (cons 't (cons 'a empty)) empty)))
>
>
> (check-expect (arrangements (cons 'a (cons 't (cons 'z empty))))
>               (cons (cons 'a (cons 't (cons 'z empty)))
>               (cons (cons 't (cons 'a (cons 'z empty)))
>               (cons (cons 't (cons 'z (cons 'a empty)))
>
>               (cons (cons 'a (cons 'z (cons 't empty)))
>               (cons (cons 'z (cons 'a (cons 't empty)))
>               (cons (cons 'z (cons 't (cons 'a empty))) empty)))))))
>
>
> (generate-report)
>
>
>
> Thank you
> Veer
>
>>  Usually we use the testing.ss teachpack like this:
>>   (check-expect (arrangements '(a t))
>>                 '((a t) (t a)))
>>  followed by
>>   (generate-report)
>>  at the very end. (This will go away in 4.0.)
>
>
>
> On Thu, Apr 3, 2008 at 7:20 PM, Matthias Felleisen  
> <matthias at ccs.neu.edu> wrote:
>>
>>  Tests should be formulated as
>>   expression
>>   expected result
>>
>>  Usually we use the testing.ss teachpack like this:
>>   (check-expect (arrangements '(a t))
>>                 '((a t) (t a)))
>>  followed by
>>   (generate-report)
>>  at the very end. (This will go away in 4.0.)
>>
>>  Why don't you do that and see what happens. -- Matthias
>>
>>
>>
>>
>>
>>
>>  On Apr 3, 2008, at 7:56 AM, richard gere wrote:
>>
>>>
>>>
>>>
>>> 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 :
>>>
>>>
>>>
>>> ;;words
>>>
>>> ;;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)
>>>  (cond
>>>    [(empty? a-word) 0]
>>>    [ else (+ 1 (length1 (rest a-word)))]))
>>>
>>> ;;tests
>>> ;;(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)
>>>  (cond
>>>
>>>    [(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)))]))
>>>
>>> ;;tests
>>> ;;(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)
>>>  (cond
>>>    [(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))]))
>>>
>>>
>>> ;;tests
>>> ;;(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)
>>>  (cond
>>>    [(empty? alow) empty ]
>>>    [else (append (for-all-pos (length1 (first alow)) (first alow)  
>>> a-sym)
>>>          (insert-everywhere/in-all-words a-sym (rest alow))) ]))
>>> ;;tests
>>> ;;(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)
>>>  (cond
>>>    [(empty? a-word) (cons empty empty)]
>>>    [else (insert-everywhere/in-all-words (first a-word)
>>>                                         (arrangements (rest a- 
>>> word)))]))
>>>
>>>
>>> ;;tests
>>> ;;(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 !!!
>>>
>>>
>>>
>>> Thanks
>>>
>>> Veer
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>>
>>
>>



Posted on the users mailing list.