[plt-scheme] Word permutations - with a slight twist
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