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

### Generating All Permutations of a Set

```
Date: 05/11/2000 at 06:21:43
Subject: Permutations (non-recursive)

Dr. Math,

How can I write out all the permutations of a set of objects in a
non-recursive way?

For example, one method I thought of was to keep "pushing" the last
element in the set to the end and then starting again until you get to
the original set.

ABCD (push d)
ABDC    "
DABC (push c)
DACB    "
DCAB    "
CDAB (push b)
CDBA    "
CBDA    "
BCDA (push a)
BACD    "
ABCD (original set)

However, this only gives 12 permutations. There should be 4! = 24
permutations.

Thanks.
```

```
Date: 05/11/2000 at 08:28:58
From: Doctor Mitteldorf
Subject: Re: Permutations (non-recursive)

Recursion is really useful for a situation like this, in which you
don't know how many code loops you have embedded. If you limit
yourself to the case of 4, you might try something like this (in
PASCAL):

var s,t,u,v :char;

begin
for s:='A' to 'D' do
for t:='A' to 'D' do
if (t<>s) then
for u:='A' to 'D' do
if (u<>s) and (u<>t) then
for v:='A' to 'D' do
if (v<>s) and (v<>t) and (v<>u) then
writeln(s+t+u+v);
end.

This says try all possible combinations for each letter in turn, but
don't bother to continue if you're repeating a letter already used.
The drawback of this approach is that it's explicit for 4 letters, and
you'd have to write a different code for 5 or 3.

You can write a general "counting" algorithm that goes AAAA, AAAB,
AAAC, AAAD, AABA, AABB, etc., then throw out all the results that
contain repeats; this isn't hard, but it's quite inefficient.

- Doctor Mitteldorf, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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