Cartesian product of several vectors

2
votes

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?

1
c++mathuniquevectorcombinations
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
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
The common name for this operation is the "Cartesian product". – Jim Lewis
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
Just out of curiosity, what do you need this for? – Nordlöw

1 Answers

12
votes

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;