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

On Jan 18, 1:51 pm, Danny Yoo <d... at hkn.eecs.berkeley.edu> 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.
>

Ahhh but does the plot not thicken if our alphabet is

{"ab","ba"}

and we have to generate all strings of 7 or less characters from this
alphabet.

How do you express the terminating condition?