Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Generating All Permutations of a Set


Date: 05/11/2000 at 06:21:43
From: Brad Harris
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    "
     ADBC    "
     DABC (push c)
     DACB    "
     DCAB    "
     CDAB (push b)
     CDBA    "
     CBDA    "
     BCDA (push a)
     BCAD    "
     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)

Dear Brad,

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/