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

 From: Danny Yoo (dyoo at hkn.eecs.berkeley.edu) Date: Thu Jan 18 08:51: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]

```
On Wed, 17 Jan 2007, wooks wrote:

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

Hi Wooks,

Let me try speaking my thoughts out loud when I see something like this.

First, how do we construct the example above?  I can sorta see how we do
it by just randomly doing things, but let's play with this a bit more.

Let me give a name to the list of all words of length 4.  I'll call it
L(4) to be concise, but you can use whatever name you want.

Is it possible that L(4) is built up of smaller versions of L?  What would
L(3) or L(2), or even L(1) look like?

L(1) = '(b)
L(2) = '(aa bb)
L(3) = '(aab baa bbb)

Ok.  I'm getting the feeling that, when we design our function, the
induction shouldn't be based on the alphabet or word structure, but rather
on the length n of the words we're generating.  Concretely, when we're
building L(3), we can reuse the definitions for smaller values of N.

Try it: can you try describing L(3) in terms of L(2) and L(1)?

By the way, this style of problem that you're tackling is described under
HTDP as "generative" recursion:

http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-32.html#node_chap_25

so if you go through Chapter 25/26, you should be in good shape to handle
it.

```

 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]