• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to generate the combinations  RSS feed

 
James Tharakan
Ranch Hand
Posts: 580
Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
...
....


Somebody please guide me
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Somebody please guide me


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
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seems pretty straight-forward using recursion; what have you come up with so far?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!