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

Danny Yoo wrote:

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

I'd had planned to read yours and Noels reply later after walking away
from the problem for a while, satisfied in the knowledge that at least
it was a straightforward problem.

So there was I stuffing my face in the kitchen last night when for some
reason I thought back to the famous HTDP problem 12.2.4. We start with

(aa b)

Now successively  prepend each element of our alphabet to this list
whilst observing the 4 character word rule

(aaaa aab baa bb)

(aaaa aabb baab bbaa bbb)

(aaaa aabb baab bbaa bbbb)

I don't think being in an environment where everything is done in Java
is helping the way I approach these problems.