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