programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# How to generate the combinations

James Tharakan
Ranch Hand
Posts: 580
I am struck with a problem...
I need to write a program which should pick up 'n' elements from 'n' number of arrays, but only one from each array at a time.( all combination)
Hope i am clear.
i.e
I don't know how many arrays are present and what is the size of each array . I would come to know about the number and size of the array during the execution time.
Once i know the required data, i need to generate all the combination.
EX:
ARRAY 1: 1,2,3
ARRAY 2 : 4,5,6,7
ARRAY 3: 8,9

So the output should be :
1,4,8
1,4,9
1,5,8
...
....

Henry Wong
author
Sheriff
Posts: 23295
125

I am assuming that you just learned about recursion. you should review that a bit -- as that is the technique that will solve this problem.

Henry

David Newton
Author
Rancher
Posts: 12617
Seems pretty straight-forward using recursion; what have you come up with so far?

fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
i see Henry has beat me to it AGAIN...

But here's another hint along his lines. This problem would be easy if you already had every possible combination for the sets 1 through n-1 (call this a 'Superset' S). Then all you'd have to do is get each element in turn from set N, and combine it with every element in S.

in other words, if you had

a = 1,2
b = 3,4
c = 5

if you could get the set with { {3,5}, {4,5} } (everything from just sets b and c), take each element in turn from a and add it to this set... so add '1' to all these giving { {1,3,5}, {1,4,5} } (but leave the original set alone), and save these off somewhere

then add '2' to each element, giving { {2,3,5}, {2,4,5} }, and add those to where you saved off your '1' elements, giving you:

{ {1,3,5}, {1,4,5}, {2,3,5}, {2,4,5} }

and you're done.