Last semester, students had difficultly understanding how to deal with
permutations, so I wrote up a quick explanation to help...

A Permutation Primer
--------------------

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 ordering 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.

The basic idea is that the array starts ordered with the smallest digit on the
left and a largest digit on the right. This is the smallest permutation, and
the largest is the exact inverse. So the algorithm finds the subarray which
represents the largest permutation, swaps in an element from the left of this
array (which must be smaller than all the elements in that array) and inverts
that subarray, creating the next ascending permutation. This goes on until we
all the way from the smallest permutation until the very largest, in order.
Hard to explain much more than that; read the algorithm.

  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.