It's not a secret anymore!*
The moose likes Programming Diversions and the fly likes combination generator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "combination generator" Watch "combination generator" New topic
Author

combination generator

ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Need a combination generator. Say you have 10 numbers and you need to generate all possible groups of 4 numbers.

Finding total number of combination is easy - 10*9*8*7/4*3*2*1 = 210.

But I want to print (get) all possible combination.

Any inputs?

Thanks.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
This would be kind of close. See if you can make it work in Java. What do you think is wrong with it and how could you fix it?


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
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Originally posted by Stan James:
This would be kind of close. See if you can make it work in Java. What do you think is wrong with it and how could you fix it?




I guess, the only problem is, it will generate duplicate combination in case array contains duplicate values.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[ankur]: I guess, the only problem is, it will generate duplicate combination in case array contains duplicate values.

Well, when you calculated the number of combinations for all possible groups of 4 numbers chosen from 10, you implicitly assumed that the 10 numbers did not contain any duplicates. Or at least, the calculation you gave will be incorrect if there are any duplicates. For example, what if the array contains 10 copies of the same number? How many combinations are possible then? I would suggest that, for now, you continue to assume that there will be no duplicates, and get a good solution to that problem. When you've got that working well, consider how to modify the solution to handle duplicates.

Meanwhile there's another problem to consider: does order matter? You used the word "combination", which normally implies that the order does not matter. And you calculated 10*9*8*7/4*3*2*1 using a formula that assumes order does not matter, consistent with the word "combination". Great. However Stan's algorithm above can give you two "different" combinations like [1 2 3 4] and [4 3 2 1] - should it? Can you find a way to prevent this from happening?

For what it's worth, there is a fairly simple way to modify Stan's algorithm above to remove listings with the same numbers in a different order. It's also possible to further modify this to handle duplicate numbers and keep track of how many times each duplicate has been used, but that's somewhat more complicated, so just consider the no-duplicate case first.


"I'm not back." - Bill Harding, Twister
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830


This works correctly, it seems.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Glad to hear you made it do what you want! I guess you did not want [1 2 3 4] and [4 3 2 1] both in your output.
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Originally posted by Stan James:
Glad to hear you made it do what you want! I guess you did not want [1 2 3 4] and [4 3 2 1] both in your output.


Yes. Thank you and Jim for the guidence!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: combination generator
 
Similar Threads
Problem from the book
How to Generate Unique Random Numbers?
java uniqueId creation
Adding numbers...