Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Permutations Generator

P. Sagdeo
Ranch Hand
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
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!

fred rosenberger
lowercase baba
Bartender
Posts: 12234
36
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
Posts: 24212
35
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
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
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
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.
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