# combination generator

ankur rathi

Ranch Hand

Posts: 3830

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 9 years ago

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

Posts: 3830

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 9 years ago

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

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

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 9 years ago
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

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.