Generating Permutations With a Computer

Date: 06/20/2002 at 12:46:34
From: Fred Gonzaga
Subject: Statistics (Permutation or Combinations)

My teenage nieces keep beating me in the word puzzle 'Jumble'.  I've
tried using alphabet blocks to be able to shuffle the letters quickly
and come up with an answer, but to no avail.

Since I have a programming background, I've decided that I will write
a computer program which for sure will beat my nieces.  But I can not 
find a formula that I can program which will take a collection of
letters (.e.g., 'TCA'), and return all possible permutations, one of
which I will recognize as a word (e.g., 'CAT'). 

Once I program this on the computer, then victory awaits me.

Thank you.

F. Gonzaga

Date: 06/21/2002 at 11:45:08
From: Doctor Ian
Subject: Re: Statistics (Permutation or Combinations)

Hi Fred,

The easiest way to write a program like this is to use recursion. 
Using the example letters 'c', 'a', and 't', you can start with 
the empty string, and the letters yet to be assigned:

  ():(c a t)

The recursive step is to check to see if you have any characters 
remaining in the unassigned list.  If you do, then you add each 
of those letters in turn to the assigned list, and then turn 
around and send each of those to the same function:

  ():(c a t)   

     ->  (c):(a t)

         ->  (c a):(t)

             ->  (c a t):()      Done!
      
         ->  (c t):(a)

             ->  etc.

     ->  (a):(c t)

         ->  etc.

     ->  (t):(a c)

         ->  etc. 

(If you haven't done any recursive programming, this is your 
chance to learn about it!)  

This is easiest in a language like Lisp, where you can just make 
up data structures on the fly by constructing nested lists, and 
which handles allocation and deallocation of memory automatically; 
and more complicated in a language like C++, where you have to set up
structures, pointers to those structures, allocation and deallocation
methods, and so on.  

In fact, an entire Emacs Lisp program to generate the 
permutations of a set of characters would look like this:

  (defun extend (s)
    (mapcar '(lambda (x)
               (list (append (car s) (list x))
                     (drop x (cadr s))))
            (cadr s)))

  (defun permute (s)
    (cond
     ((null (cadr s))
      (list s))
     (t
      (mapcar 'permute (extend s)))))


  (defun drop (x s)
    (cond
      ((null s)
       s)
      ((eq x (car s))
       (cdr s))
      (t 
       (cons (car s) (drop x (cdr s))))))
   
  (mapcar 'permute 
          (list (list ( ) '(a b c d e))))
                       ^        ^
                       |        |
                  Initial    Unassigned 
                  (empty)    characters
                  string

The first function, extend, takes an item that looks like 

  ((a) (b c d))

and turns it into a list of items that looks like 

  (((a b) (c d))
   ((a c) (b d))
   ((a d) (b c)))

The second function, permute, takes a list of these guys, checks 
each one to see if there are any characters remaining to be 
distributed.  If not, it just returns the finished item, e.g., 

  ((a c b) ())

This is what keeps the recursion from continuing forever.  If 
there are unassigned characters, it extends each item in the 
list, and then applies itself to the new list.  

The third function, drop, removes a sincle occurrence of a letter from
a list containing multiple occurrences of that letter.  This allows
the program to handle jumbles like 'haade' ('ahead'). 

The second step, of course, would be to check the strings you 
generate this way against some kind of online dictionary.  

Does this help? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/21/2002 at 11:54:13
From: Fred Gonzaga
Subject: Thank you (Statistics (Permutation or Combinations))

Thank you for your help.  Since I do mostly VBA programming, I 
will have to figure out how I can do recursion in this language.  
Once again, thank you.

Date: 06/21/2002 at 15:04:10
From: Doctor Ian
Subject: Re: Thank you (Statistics (Permutation or Combinations))

Hi Fred,

I've never used VBA, so I'm not sure if it supports recursion.  
Some languages don't.  However, a simple way to avoid recursion 
would be to have two arrays, one for incomplete items, e.g., 

  (a c):(b d)
  
and one for complete items, e.g., 

  (a c d b):()

Then you loop through the first array, each time removing the 
first element, and either (1) moving it to the second array, 
or (2) expanding it, and placing the new elements at the end 
of the first array.  

When the first array is empty, the second array should contain 
all the permutations.  

You can avoid having to set up data structures by using 
strings, e.g., 

  ca:bde

Then the expansion function looks like this:

  If there are characters after the colon {
     for each such character {
       - remove it from after the colon 
       - place it immediately before the colon  
       - place the item on the end of the incomplete array
     }
   }
   Otherwise {
      Remove the colon and place the item on the complete array
   }
     
Have fun.  

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/21/2002 at 16:33:55
From: Fred Gonzaga
Subject: Thank you (Statistics (Permutation or Combinations))

I know how to use arrays very well, so I think I can do this using the
VBA array function.  Thanks again.