Cartesian Product in c++

Question

I have been searching for weeks on how to come up with piece of code which I could applied the cartesian product. Let's say I have two arrays :

int M[2]= {1,2};
int J[3] = {0,1,2};

So the code will takes those two arrays in apply the rule M X J therefore we will have the pairs (1,0)(1,1)(1,2)(2,0)(2,1)(2,2) and I want the new result to be saved into a new array where each index in the array contains a pair , for example c[0] = (1,0). Help please :(

Answer 1

#include <iostream>
#include <iterator>
#include <vector>
#include <utility>
#include <tuple>

template<typename Range1, typename Range2, typename OutputIterator>
void cartesian_product(Range1 const &r1, Range2 const &r2, OutputIterator out) {
    using std::begin; using std::end;
    
    for (auto i = begin(r1);i != end(r1); ++i) {
        for (auto j = begin(r2); j != end(r2); ++j) {
            *out++ = std::make_tuple(*i, *j);
        }
    }
}

int main() {
    std::vector<int> a{1,2,3};
    std::vector<char> b{'a','b','c','d','e','f'};
    
    std::vector<std::tuple<int, char>> c;
    cartesian_product(a, b, back_inserter(c));
    
    for (auto &&v : c) {
        std::cout << "(" << std::get<int>(v) << "," << std::get<char>(v) << ")";
    }
}

Prints:

(1,a)(1,b)(1,c)(1,d)(1,e)(1,f)(2,a)(2,b)(2,c)(2,d)(2,e)(2,f)(3,a)(3,b)(3,c)(3,d)(3,e)(3,f)

And you can also apply the function to your case:

template<typename T, int N> constexpr int size(T (&)[N]) { return N; }

int main() {
    int M[2] = {1,2};
    int J[3] = {0,1,2};

    std::tuple<int, int> product[size(M) * size(J)];

    cartesian_product(M, J, product);

    for (auto &&v : product) {
        std::cout << "(" << std::get<0>(v) << "," << std::get<1>(v) << ")";
    }
}

The output is:

(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)

http://coliru.stacked-crooked.com/a/3ce388e10c61a3a4

Answer 2

Here is an implementation where the sequences of values is a parameter (rather than pre-known as in all the other implementations):

void CartesianRecurse(vector<vector<int>> &accum, vector<int> stack,
    vector<vector<int>> sequences, int index)
{
    vector<int> sequence = sequences[index];
    for (int i : sequence)
    {       
        stack.push_back(i);
        if (index == 0)
            accum.push_back(stack);
        else
            CartesianRecurse(accum, stack, sequences, index - 1);
        stack.pop_back();
    }
}
vector<vector<int>> CartesianProduct(vector<vector<int>> sequences)
{
    vector<vector<int>> accum;
    vector<int> stack;
    if (sequences.size() > 0)
        CartesianRecurse(accum, stack, sequences, sequences.size() - 1);
    return accum;
}

main() {
    vector<vector<int>> sequences = { {1,2,7},{3,4},{5,6} };
    vector<vector<int>> res = CartesianProduct(sequences);
    // now do something with the result in 'res'.
}

Answer 3

Here is an simple example of implementing Cartesian product using vector. Vectors are much better choice as we do not need to worry about its size as it dynamically changes it.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
    int M[2]= {1,2};
    int J[3] = {0,1,2};
    vector<pair<int,int>> C;

    for (int i = 0; i < sizeof(M)/sizeof(M[0]); i++)
    {
        for (int j = 0; j < sizeof(J)/sizeof(J[1]); j++)
        {
            C.push_back(make_pair(M[i],J[j]));
        }  
    }

    /*
    for (vector<int>::iterator it = C.begin(); it != C.end(); it++)
    {
        cout << *it << endl;
    }

    */

    for (int i = 0; i < C.size(); i++)
    {
        cout << C[i].first << "," << C[i].second << endl;
    }
}

Here is the link where I implemented the above code. Although I wouldn't post solution directly relating to your question, links posted in the comments already contains answer which is why I posted.

Answer 4

I think using of c++ two-dimensional arrays is a very bad idea, but if you want, you probably could use this code

    #include <iostream>    
    int** cartesian_prod( int* s1, int* s2, int s1size, int s2size )
    {
        int ressize = s1size*s2size;
        int** res = new int*[ressize];
        for ( int i = 0; i < s1size; i++ )
            for ( int j = 0; j < s2size; j++ )
            {
                res[i*s2size+j] = new int[2];
                res[i*s2size+j][0] = s1[i];
                res[i*s2size+j][1] = s2[j];
            }
        return res;
    }
    int main() {
        int M[2]= {1,2};
        int J[3] = {0,1,2};
        int** res;
        int Msize = sizeof(M)/sizeof(M[0]);
        int Jsize = sizeof(J)/sizeof(J[1]);
        res = cartesian_prod(M, J, Msize, Jsize);
        for ( int i = 0; i < Msize*Jsize; i++ )
            std::cout << res[i][0] << " " << res[i][1] << std::endl;
        for (int i = 0; i < Msize*Jsize; i++)
            delete[] res[i];
        delete[] res;
        return 0;
    }

But it is much better to deal with std::vector - it much faster (in terms of development time) and will save you from many errors.

Answer 5

Solution without for loops.

#include<array>
#include<iostream>
#include<tuple>
#include<utility>

template
<typename T, typename Tuple, std::size_t... I>
auto cartesian_product_base(
                         const T& a,
                         const Tuple& t,
                         std::index_sequence<I...>) {
    return std::make_tuple(std::make_pair(a, std::get<I>(t))...);
}

template
<typename T, typename... Ts, std::size_t... I>
std::array<T, sizeof...(Ts) + 1> to_array(std::tuple<T, Ts...> t, std::index_sequence<I...>) {
    return {std::get<I>(t)...};
}

template
<typename Tuple1, typename Tuple2, std::size_t... I>
auto cartesian_product_impl(
                         const Tuple1& t1,
                         const Tuple2& t2,
                         std::index_sequence<I...>) {
    return std::tuple_cat(cartesian_product_base(
                                 std::get<I>(t1),
                                 t2,
                                 std::make_index_sequence<std::tuple_size<Tuple2>::value>{})...);
}

template
<typename T1, std::size_t N1, typename T2, std::size_t N2>
auto cartesian_product(
                     const std::array<T1, N1>& a1,
                     const std::array<T2, N2>& a2) {
    return to_array(
                    cartesian_product_impl(a1, a2, std::make_index_sequence<N1>{}),
                    std::make_index_sequence<N1 * N2>{});
}

using namespace std;

int main() {
    array<int, 2> M = {1, 2};
    array<int, 3> J = {0, 1, 2};
    auto C = cartesian_product(M, J);
    cout << C.size() << endl;
    cout << "{";
    for (size_t i = 0; i != C.size(); ++i) {
        if (i != 0) {
            cout << ", ";
        }
        cout << "(" << C[i].first << ", " << C[i].second << ")";
    }
    cout << "}" << endl;
}