-6

I am trying to implement an application . It requires the following logic. 

Set1 {1,2,3,4}
Set2 {22,44}
Set3 {8,9,11}

I need to select one number from each set. So in total,there will be 3 numbers. But there are many combinations. Each run of my application must choose different combinations for better complexity. I mean 

First run : 1 22 8
Second run : 1 44 9
And so on...

So i need to find out all the combinations between different sized sets. I know the way to find in a single set {1,2,3,4}.

I don't know any mathematics algorithms for this. Is there any logic to do it in Java or C or C++. Any ideas generally?

EDIT

Expected output is:

1 22 8
1 22 9
1 22 11
1 44 8 
1 44 9 
1 44 11
2 22 8
2 22 9
and so on
Spikatrix
  • 20,225
  • 7
  • 37
  • 83
Gibbs
  • 21,904
  • 13
  • 74
  • 138
  • 1
    There are functions to get the random number, so what you could do is random a number from 0 to n (where n is number of possible sets) and choose this set, it really depend what you want to do, you need to be more descriptive. My solution will give you equal possibility of sets, however it may not be what you want. – cerkiewny Jul 03 '14 at 11:41
  • 1
    If my tags are wrong , please let me know. I ll edit it. My aim is only idea not the code – Gibbs Jul 03 '14 at 11:42
  • Recursion. You know how to do it for a single set; the way to do it for k >= 2 sets is to pick a random element x from the first set, and then call yourself with the remaining k-1 sets to find a set of k-1 representatives from those sets, and finally insert x into this set. – j_random_hacker Jul 03 '14 at 11:43
  • @cerkiewny i ll edit my question further. – Gibbs Jul 03 '14 at 11:44
  • 2
    I think I need more coffee, I just wrote up an answer in Python... then realized this was tagged C++. – Cory Kramer Jul 03 '14 at 11:45
  • If the number of set is always know (3 in your question), you could simply do it with 3 nested for loops. – Syam S Jul 03 '14 at 11:52
  • I specified in my question it is n. Not a fixed one.Could anybody please explain the reason for negative voting? – Gibbs Jul 03 '14 at 11:53
  • Are you asking how many combinations there are in total? Or how to write code to find a combination? – doctorlove Jul 03 '14 at 11:58
  • @Cyber it's tagged Java too and C - just edit the tags ;-) – doctorlove Jul 03 '14 at 11:58
  • I need what are the combinations , not the count. – Gibbs Jul 03 '14 at 12:00
  • @Cyber Before going to fetch the next cup, behold yourself. I think the OP should have better tags. At least it shouldn't have damaged much, to post the python solution, since the OP doesn't ask for code, but the _algorithm_ LOL! ;) – πάντα ῥεῖ Jul 03 '14 at 12:42

3 Answers3

3

You can use cartesian product on sets in Java by the use of com.google.common.collect.Sets.

FOR EXAMPLE

  Set<Integer> s1=new HashSet<Integer>();
  s1.add(1);s1.add(4);s1.add(5);

  Set<Integer> s2=new HashSet<Integer>();
  s2.add(2);s2.add(3);s2.add(6);

  Set<Integer> s3=new HashSet<Integer>();
  s3.add(7);s3.add(8);s3.add(8);

  Set<List<Integer>> set=Sets.cartesianProduct(s1,s2,s3);
  //Give type safety warning
  for(List<Integer> l:set){
      System.out.println(l);
  }

OUTPUT

[1, 2, 7]
[1, 2, 8]
[1, 3, 7]
[1, 3, 8]
....

NOTE

If you want exact output as 1 2 7 for that you just need to Override toString method of List

Community
  • 1
  • 1
akash
  • 22,664
  • 11
  • 59
  • 87
1

Assuming you don't care about the order and you want to get all combinations you could do something as simple as:

for (auto it1 : set1)
for (auto it2 : set2)
for (auto it3 : set3)
{
   //do stuff with *it1, *it2, *it3
   //e.g. printing them
   std::cout << *it1 << *it2 << *it3 << std::endl;
   //gives you exactly the listing you want
}
Lanting
  • 3,060
  • 12
  • 28
  • I don't want to manipulate them them . just need the lists as i mentioned in my edit – Gibbs Jul 03 '14 at 11:51
  • listing them sort of requires iterating them – Lanting Jul 03 '14 at 11:53
  • Yeah :) Lanting. Edited – Gibbs Jul 03 '14 at 11:54
  • Yeah :) It has (sizeofset1)*(sizeofset2)*(sizeofset3) complexity. I need an efficient way – Gibbs Jul 03 '14 at 11:57
  • There isn't a more efficient way.. You have to iterate over each combination. – Daniel Kleinstein Jul 03 '14 at 11:58
  • Doesn't it kind of makes sense that given there are actually (sizeofset1)*(sizeofset2)*(sizeofset3) combinations, the complexity is also of (sizeofset1)*(sizeofset2)*(sizeofset3)? – Lanting Jul 03 '14 at 11:59
  • It's rather hard to list (sizeofset1)*(sizeofset2)*(sizeofset3) things using less than (sizeofset1)*(sizeofset2)*(sizeofset3) steps. – doctorlove Jul 03 '14 at 11:59
  • @Lanting if you're using `auto` you're using `C++11`, but then why not simply do `for ( auto i0 : set1 ) { for ( auto i1 : set2 ) { ... std::cout << i0 << i1 << i2 << "\n" } }`? – stefan Jul 03 '14 at 12:00
  • I thought there must be an efficient way after [reading this](http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/). – Gibbs Jul 03 '14 at 12:00
  • But that's drawing from the same 'set' and assuming the order by which you draw the numbers during a turn isn't important (i.e. (1,2,3) = (3,2,1)). In your example you're using 3 distinct sets that have an empty intersection and your example output is simply the Cartesian product. It's not going to get any faster. – Lanting Jul 03 '14 at 12:08
  • @stefan, because I'm stuck with gcc 4.4 – Lanting Jul 03 '14 at 12:16
1

You could do it quite simply with three for loops, assuming all you want is to output the possible combinations.

for(int i = 0; i < set1.size; i++){
   for(int j = 0; j < set2.size; j++){
      for(int k = 0; k < set3.size; k++){
         System.out.println(set1.toArray()[i] + " " + set2.toArray()[j] + " " + set3.toArray()[k]);
         // toArray() represents the set as an array, allowing easy access to its indices
      }
   }
}

That would yield your listed output in a simple way, and you could probably easily see how it works. For fixed values from set1 and set2, output all possibilities from set3. Then change to another unused value from set2, and so on.

MikeM
  • 342
  • 2
  • 10