[plt-scheme] Word permutations - with a slight twist

From: Noel Welsh (noelwelsh at yahoo.com)
Date: Thu Jan 18 07:46:05 EST 2007

I did something similar recently to generate all the
indexes of an array of statically unknown dimension.

I suggest you start by writing the procedure that, given a
list of symbols, generates all the one-step permutations.

E.g. Given

  '(aa bb)

generate

  '(aaaa bbaa aabb bbbb)

The full permutation function is a fairly straightforward
generalisation of this.  Follow the design recipe and you
should be ok.

I don't want to give too much help on a public forum as
this is a common homework question.

HTH,
Noel

--- wooks <wookiz at hotmail.com> wrote:

> 
> This is not homework
> 
> Construct a list of all words of length n that can be
> generated from
> the following 2 letter alphabet
> 
>  (list aa b)
> 
> Example where n = 4  '(aaaa aabb baab bbaa bbbb)
> 
> I chose to represent the letters of the alphabet as a
> list because you
> can't get the length of a symbol
> 
> A list-of-symbols(los) is either
>    empty or
>    (cons sym los)
> 
> 
> An n-word is either
>   empty or
>   cons (los x-word)
> where x-word is an n-word of length n - length(los)
> 
> (cons (list 'a 'a)
>       (cons (list 'b)
>             (cons (list 'b)))
> 
> (cons (list 'a 'a)
>       (cons list 'a 'a)
> 
> (cons (list 'b)
>       (cons (list 'a 'a)
>             (cons (list 'b)
> 
> Yeesss. Doesn't feel very right.
> 
> n-word doesn't say how long it should be. So perhaps we
> need a
> structure
> 
> (define-struct n-word (letters length))
> 
> So now letters would have to be a list-of-list-of-symbols
> and a
> constructor really ought to check that
>  (=  (length (n-word letters))
>       (length (n-word length)))
> 
> but (make n-word ....) doesn't do that.
> 
> Another idea that occurs is to substitute letters of
> length > 1 in the
> alphabet with a symbol of length 1 that represents it but
> that seems
> like evil hacking.
> 
> I feel I'm chasing my own tail on this one.
> 
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 


Email: noelwelsh <at> yahoo <dot> com   noel <at> untyped <dot> com
AIM: noelhwelsh
Blogs: http://monospaced.blogspot.com/  http://www.untyped.com/untyping/


 
____________________________________________________________________________________
Need a quick answer? Get one in minutes from people who know.
Ask your question on www.Answers.yahoo.com


Posted on the users mailing list.