From barr@CS.Cornell.EDU Sat Jan 30 18:45:53 1999
Date: Sat, 30 Jan 1999 18:45:37 -0500 (EST)
From: Rimon Barr <barr@CS.Cornell.EDU>
To: Rimon Barr <barr@CS.Cornell.EDU>
Newsgroups: cornell.class.cs202
Subject: Permutations.


Seems that the concept of a permutation is giving people trouble. So I'll
try to provide some pseudocode to help.

Generating permutations is not hard at all if you think of it in the right
way. I'll outline three methods below.

Method #1:
----------
Basically what you are looking for is a number where each digit is stored
in a separate array element. And the valid numbers are those that don't
have any digits repeated. If you are looking for permutations of size n,
then the number is going to have n digits and each digit will range from 0
to n-1. So that's basically it right there.
Start with an array filled with: 0 0 0 0 0 0 ... 0
and count up to : (n-1) (n-1) (n-1) ... (n-1).
For each number you need to check that there are no duplicate digits,
which is not that hard. If there are no duplicate digits you have a valid
permutation. Just keep going until you get all of then.

Method #2:
----------
Of course, the algorithm above is naive and very inefficient. There will
be many numbers that are discarded and it may take a long time to cycle
through this large space of numbers and check each one.

So let's just generate valid numbers. You start the algorithm with a bag
of numbers (all the numbers from 0 to n-1) and then follow the recursive
definition below. 

  permute (bag, array)
    if isEmpty(bag)
      print array
    else
      for each number in bag
        remove number from bag
        place number at end of array
        permute(bag, array)
        remove number from end of array
        put number back in bag
      end for
    end if

It's quite easy to represent a "bag" of numbers with a new array of
numbers that you pass forward. Then you don't have to "put the number
back" after you are done. Also, it's quite easy to seed the algorithm with
a preexisting array and permute up one at a time.

Method #3:  
---------- 
This is the trickiest algorithm, so don't use it unless you understand it,
because it will be hard to debug. It basically uses some properties of the
array to unroll the recursion without even using a stack! The stack is
stored implictly in the array. Proving it's correct is lengthy, but if you
stare at it a little, you should understand how it works.

  array <- permute (array a)
    if for all i, a[i]>a[i+1] then
      this is the largest permutation already!
    find largest i such that a[i]<a[i+1]  (ie. search backwards)
    find largest j, greater than i, such that a[i]<a[j]
    swap a[i], a[j]
    reverse order of elements in a[i+1..end]

I don't recommend implementing Method #1. The code for #2 and #3 is about
the same length, but method #2 is a lot easier to understand. I hope this
helps. If anyone notices that I've made an error in the pseudo-code please
email me.

All the best,
Rimon.
-- 
  *
  |  Rimon Barr, Ph.D. student, Computer Science, Cornell University.
  |  Email: barr@cs.cornell.edu
  |  WWW:   http://www.cs.cornell.edu/home/barr/
  |
  | "Remember no man is a failure who has friends."
  |                          -- Clarence Odbody, It's a Wonderful Life
  +----