# [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?