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

From: wooks (wookiz at hotmail.com)
Date: Thu Jan 18 02:13:40 EST 2007

This is not homework

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)

I chose to represent the letters of the alphabet as a list because you
can't get the length of a symbol

A list-of-symbols(los) is either
   empty or
   (cons sym los)

An n-word is either
  empty or
  cons (los x-word)
where x-word is an n-word of length n - length(los)

(cons (list 'a 'a)
      (cons (list 'b)
            (cons (list 'b)))

(cons (list 'a 'a)
      (cons list 'a 'a)

(cons (list 'b)
      (cons (list 'a 'a)
            (cons (list 'b)

Yeesss. Doesn't feel very right.

n-word doesn't say how long it should be. So perhaps we need a

(define-struct n-word (letters length))

So now letters would have to be a list-of-list-of-symbols and a
constructor really ought to check that
 (=  (length (n-word letters))
      (length (n-word length)))

but (make n-word ....) doesn't do that.

Another idea that occurs is to substitute letters of length > 1 in the
alphabet with a symbol of length 1 that represents it but that seems
like evil hacking.

I feel I'm chasing my own tail on this one.

Posted on the users mailing list.