This week's book giveaway is in the Cloud/Virtualizaton forum.We're giving away four copies of Mesos in Action and have Roger Ignazio on-line!See this thread for details.
Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# combination generator

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

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

ankur rathi
Ranch Hand
Posts: 3830

This works correctly, it seems.

Stan James
(instanceof Sidekick)
Ranch Hand
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
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!