0

I am having a problem: There are several sets of numbers and I need to find all combinations of them where I choose just one value from each set. First element from the first set, second element from the second set, etc. For example:

Set1 - {1, 2, 3}
Set2 - {4, 5, 6, 7}
Set3 - {8, 9, 10}

The result should be: 

1, 4, 8
1, 4, 9
1, 4, 10
1, 5, 8
1, 5, 9
1, 5, 10
...
3, 7, 9
3, 7, 10

I have written a simple recursive algorithm. My algorithm is much like the accepted answers of Howto create combinations of several vectors without hardcoding loops in C++? and generate all combination of elements in 2d vector.

But this solution is not effective for large sets. It requires about size1*size2*size3 complexity to get the result and for larger sets (more than 100 elements) it starts to consume a lot of CPU resources. Is there any other method or approach for finding all the combinations, that will work faster and will be optimal for larger sets?

P.S. I have written my algorithm in C++, but any language is welcomed for examples.

EDIT :

I need to find all those combinations that satisfy a specific condition, which looks like something (A>1) && (B>2) && (C>3). Which means that if at least one value from set A is more than 1, and at least one value from set B is more than 2, and at least one value from set C is more than 3.

Community
  • 1
  • 1
nabroyan
  • 3,225
  • 6
  • 37
  • 56
  • 5
    If you want to enumerate all the combinations it will obviously requires as much iteration as there are combinations. You cannot go down below `size1*size2*...*sizeN`. If you want to compute something *over* the set of all combinations then you should says so, because indeed there may be possibility to do so with lower complexity (for instance: counting the number of combinations or summing their values). – fjardon Oct 09 '15 at 13:25
  • 2
    So when your output size is size1*size2*size3, why do you expect an algorithm that does better than that? – user3528438 Oct 09 '15 at 13:26
  • This is no algorithm which have complexity better than size1*size2*...*sizeN Because this is size of result set. Could you please share information what you plan to do with these sets? – Толя Oct 09 '15 at 13:33
  • For each combination separately I need to check for a predefined condition and if that condition is satisfied I need to perform some action (like show a warning message). – nabroyan Oct 09 '15 at 13:37
  • 1
    Could you share condition, because maybe not necessary iterate all sets, just maybe possible generate only required sets instead of all. – Толя Oct 09 '15 at 13:41
  • That condition is defined by a user, but it looks like something like this (A>1) && (B>2) && (C>3), which means that if at least one value from set A is more than 1, and at least one value from set B is more than 2, and at least one value from set C is more than 3. – nabroyan Oct 09 '15 at 13:47
  • Please add a condition example to your question (and the expected output). – MrSmith42 Oct 09 '15 at 15:41
  • You don't want to find "all combinations", as your question indicates; you cannot do that in less time than it takes to enumerate all combinations. What you want to find is "those combinations which satisfy a condition", and the algorithm to do that will depend on the condition. You should probably ask a different question which includes the specific condition you want to analyze. – rici Oct 09 '15 at 16:18
  • @rici I have edited my question. – nabroyan Oct 09 '15 at 16:37
  • If the results have to satisfy a condition like `(A>1) && (B>2) && (C>3)`, could you not simply filter the sets first, and then generate the combinations? In the example that would mean removing 1 from the first set, and then finding all combinations of { 2, 3}, {4, 5, 6, 7} and {8, 9, 10}, which would number 24 instead of 36? – m69's been on strike for years Oct 12 '15 at 22:07
  • Actually I do that kind of filtering, but sometimes all conditions are true for all variable, in those case over-heading is present. – nabroyan Oct 13 '15 at 14:14

0 Answers0