Associated Topics || Dr. Math Home || Search Dr. Math

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

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

(defun permute (s)
(cond
(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 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.
```
Associated Topics:
High School Calculators, Computers
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search