[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)


  '(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.


--- 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.