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

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.