aspose file tools*
The moose likes Beginning Java and the fly likes Permutations Generator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Permutations Generator" Watch "Permutations Generator" New topic
Author

Permutations Generator

P. Sagdeo
Ranch Hand

Joined: Nov 13, 2003
Posts: 67
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
Dirk Schreckmann
Sheriff

Joined: Dec 10, 2001
Posts: 7023
Parth S.,
Welcome to JavaRanch!
We ain't got many rules 'round these parts, but we do got one. Please change your display name to comply with The JavaRanch Naming Policy.
Thanks Pardner! Hope to see you 'round the Ranch!


[How To Ask Good Questions] [JavaRanch FAQ Wiki] [JavaRanch Radio]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11309
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24184
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
chi Lin
Ranch Hand

Joined: Aug 24, 2001
Posts: 348
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
Gillian Bladen-Clark
Greenhorn

Joined: Dec 13, 2003
Posts: 18
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Permutations Generator