Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Permutations Generator

 
P. Sagdeo
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7023
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12146
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24211
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
chi Lin
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic