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

 From: Noel Welsh (noelwelsh at yahoo.com) Date: Thu Jan 18 07:46:05 EST 2007 Previous message: [plt-scheme] Re: Word permutations - with a slight twist Next message: [plt-scheme] Re: Word permutations - with a slight twist Messages sorted by: [date] [thread] [subject] [author]

```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. Previous message: [plt-scheme] Re: Word permutations - with a slight twist Next message: [plt-scheme] Re: Word permutations - with a slight twist Messages sorted by: [date] [thread] [subject] [author]