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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.