Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# combination generator

Ranch Hand
Posts: 3851
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.

(instanceof Sidekick)
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: 3851

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.

Wanderer
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: 3851

This works correctly, it seems.

Stan James
(instanceof Sidekick)
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: 3851

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!

 Everybody's invited. Even this tiny ad: Thread Boost feature https://coderanch.com/t/674455/Thread-Boost-feature