2

similar questions have been asked before but I cant find an exact match to my question.

I have 4 vectors each of which hold between 200-500 4 digit integers. The exact number of elements in each vector varies but I could fix it to a specific value. I need to find all possible combinations of the elements in these 4 vectors.

eg:

v1[10, 30] v2[11, 45] v3[63, 56] v4[82, 98]

so I'd get something like this:

[10, 11, 63, 82]; [30, 11, 63, 82]; [10, 45, 63, 82]; [10, 45, 56, 82] etc..

Is there a common name for this algorithm so I can find some references to it online? Otherwise any tips on implementing this in C++ would be helpful. Performance isn't much of an issue as I only need to run the algorithm once. Is there anything built into the STL?

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
Stephen Blinkhorn
  • 637
  • 2
  • 7
  • 17
  • 2
    Beware that there will be between 200^4 and 500^4 combinations. 500^4 is 62.5 billion and 200^4 is over 1 billion. – Peter Alexander Mar 08 '10 at 22:37
  • 4
    Wait, if you just had 2 with v1={1,1,2} and v2={1,2}, do you want {1,2} to appear in the output twice? Also, do you consider {1,2} and {2,1} to be the same? – Peter Alexander Mar 08 '10 at 22:39
  • 13
    The common name for this operation is the "Cartesian product". – Jim Lewis Mar 08 '10 at 22:40
  • Good questions Poita. There are no duplicate entries within any one vector although there could be duplicate entries across vectors. I don't consider {1,2} and {2,1} to be the same but removing such occurrences would be advantageous. – Stephen Blinkhorn Mar 09 '10 at 14:06
  • "Would be advantageous"? You really need to specify exactly what you want before you start writing code. – Potatoswatter Mar 10 '10 at 08:11
  • "Would be advantageous" suggests something that could be beneficial but not entirely critical. – Stephen Blinkhorn Mar 11 '10 at 02:04
  • The astute amongst you may have noticed that the recent change to the question's title has now rendered part of the question obsolete eg "Is there a common name for this algorithm so I can find some references to it online". In the excitement of the moment the editor must have overlooked this. Also, where did answer 2 go? – Stephen Blinkhorn Mar 11 '10 at 02:09
  • 1
    Just out of curiosity, what do you need this for? – Nordlöw Oct 29 '11 at 16:24
  • http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors this thread presents some good solutions for the general case. – Kos Dec 23 '11 at 20:44

1 Answers1

12

Not much of an algorithm...

for(vector<int>::const_iterator i1 = v1.begin(); i1 != v1.end(); ++i1)
    for(vector<int>::const_iterator i2 = v2.begin(); i2 != v2.end(); ++i2)
        for(vector<int>::const_iterator i3 = v3.begin(); i3 != v3.end(); ++i3)
            for(vector<int>::const_iterator i4 = v4.begin(); i4 != v4.end(); ++i4)
                cout << "[" << *i1 << "," << *i2 << "," << *i3 << "," << *i4 << "]" << endl;
Andrew Stein
  • 12,880
  • 5
  • 35
  • 43