Hello. I need to create a permutations generator for a program that I am going to write. You would input how many numbers and it should output all the combinations (input 3 : output : 0,0,0 0,0,1 0,0,2 0,1,0 0,1,1 0,1,2 0,2,0 0,2,1 0,2,2 1,0,0,etc). Anyone know of any good algorithms or something to get me started. I'm not sure where to begin. Thanks, Parth
i'm not sure i understand the question. is the "3" of the input the number of digits you want to output, the limit of how high each position should go, or both? but basically you should be able to do this with a couple of nested loops. this is basically like a car odometer. each loop represents a digit you want displayed - the outermost loop is the most significant position, down to the innermost being the least significant. then, inside the innermost, just print the counter for each loop. that should generate all possible combinations.
Never ascribe to malice that which can be adequately explained by stupidity.
author and iconoclast
It's actually a little trickier than Fred's "nested loops" because the number of loops -- the nesting depth -- isn't known at compile time. Here's a Java implementation of Dijkstra's algorithm for generating permutations.
I have a program that does this with a pattern: blah*blah*blah*blah It replaces each * with a number and generates permutations. My approach was to replace nested loops with recursion. The routine replaces the first * it finds with a number. If there are any * remaining, it calls itself, otherwise it publishes the result. You could replace the pattern business with a simple parameter telling you how many positions to generate. To be truyly generic you might pass an array of domains - descriptions of valid values at each position. Any of that help?
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Joined: Jan 30, 2000
Be aware that "permutations" and "combinations" mean different things, and I'm not sure that either is what you want. If I have three numbers 0, 1, 2, the permutations would be 0, 1, 2 0, 2, 1 1, 0, 2 1, 2, 0 2, 0, 1 2, 1, 0 Here we change the order that the elements appear in, but we don't change the number of times the element appears - each occurs just once. Though we could discuss the permutations of the list (0, 0, 0, 1, 1, 1, 2, 2, 2 ) taking just three elements... Urm, this could get to be ain involved discussion, and I'm not sure it's really necessary. The problem originally posed has a solution considerably simpler than Dijkstra's algorithm. It might be useful to write one simple program to show output for n = 2, then write another program for n = 3, then n = 4. Each time you increase n you'll add a nested loop. Then see if you can find a way to generalize this program by writing a method for an arbitrary n. This might be a good place to use a recursive method call. Good luck...
"I'm not back." - Bill Harding, Twister
Joined: Aug 24, 2001
Parth, If I understand your question correct, the relationship between total possible patterns & the number n is like toatal possible combination = n^n for n =3, you have 3^3 = 27 patterns range from 000 to 222 <- base 3 which equal 0 to 26 in decimal. to get all the 27 patterns, you can use Integer.toString(i, 3) inside a for loop with i range 0 - 26 the output will be 1,2,10,11,12,20 .... 222. next task will be 1. pad zero to get the pattern like 001, 002 , 010 2 parameter to for loop, radix to be flexible. HTH
Originally posted by Parth S.: Hello. I need to create a permutations generator for a program that I am going to write. You would input how many numbers and it should output all the combinations (input 3 : output : 0,0,0 0,0,1 0,0,2 0,1,0 0,1,1 0,1,2 0,2,0 0,2,1 0,2,2 1,0,0,etc). Anyone know of any good algorithms or something to get me started. I'm not sure where to begin. Thanks, Parth
Joined: Dec 13, 2003
Excellent neat solution of this problem can be found in the solutions to exercises for the book Beginning Java 2 SDK 1.4 Edition at http://www.wrox.com/dynamic/books/download.aspx. (chapter 10 sol 4). The clever bit is done with a recursive method - just a dozen or so lines of code. You don't need to buy the book to understand the solution, but I put a few println's in so that you can see how it builds the results recursively.