P. Sagdeo

Ranch Hand

Posts: 67

posted 13 years ago

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 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

posted 13 years ago

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!

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!

posted 13 years ago

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.

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

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 13 years ago

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?

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

Sheriff

Posts: 18671

posted 13 years ago

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...

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

Posts: 348

posted 13 years ago

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

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

posted 13 years ago

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.