Creating a List of Permutations with a Computer Program

Date: 07/31/2007 at 12:51:30
From: Adam
Subject: Recursion to find different orders of items

I am aware that if you have, for example, 5 items, then there are 5!
ways to arrange them.  My question is, how can I find all these
arrangements?

I am going to be writing a program in Ansi C to calculate and print
larger item number arrangements, so I need an algorithm to do this
efficiently.  I have a pattern that will get some of the combinations,
but I can't figure out one that gets all of them!  It seems that most
answers online are only concerned with how many ways can items be
arranged, not what the actual arrangements are.

To find some of the patterns you can simply move the 1st number all
the way through the list, then the second, and so on.  For example,

1 2 3 4 5
2 1 3 4 5
2 3 1 4 5
2 3 4 1 5
2 3 4 5 1
3 2 4 5 1
3 4 2 5 1
3 4 5 2 1
3 4 5 1 2
...

I am confident that the solution will involve moving a number, then
moving all the numbers to the right of that, and all the ones to the
right of that until you are at the final number.  Then repeating with
the number you started with.  I would appreciate any insight into a
possible solution.  Thanks!

Date: 07/31/2007 at 21:32:59
From: Doctor Vogler
Subject: Re: Recursion to find differnt orders of items

Hi Adam,

Thanks for writing to Dr. Math.  There are 5! ways to permute the
numbers, because there are 5 choices for the first number, 4 choices
for the second, 3 for the third, 2 for the fourth, and 1 for the
fifth.  So you can loop over all five choices for the first number (1
through 5), and then all four choices for the second number 
(everything except the first number), and all three choices for the
third (everything except the first two numbers), both choices for the
fourth (the two you haven't listed yet), and then the last number has
to be the one you didn't choose yet.

An equivalent way to list the same answers is to start with the five
numbers, chosen from 1 to 5, from 1 to 4, from 1 to 3, from 1 to 2,
and the last one is always 1.  Then look at the first number and
increase by 1 every number after it that is greater than or equal to
the first number.  Then look at the second number and increase by 1
every number after it (the third, fourth, and fifth) that is greater
than or equal to the second number.  And so on for the third and
fourth.  (Of course, there is nothing to do at the fifth number, since
there is nothing after it.)

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/