How to Create Cartesian Product of Vector of Vectors

How can I create cartesian product of vector of vectors?

First, I'll show you a recursive version.

// Cartesion product of vector of vectors

#include <vector>
#include <iostream>
#include <iterator>

// Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi)
typedef std::vector<int> Vi;
typedef std::vector<Vi> Vvi;

// Just for the sample -- populate the intput data set
Vvi build_input() {
   Vvi vvi;

   for(int i = 0; i < 3; i++) {
      Vi vi;
      for(int j = 0; j < 3; j++) {
         vi.push_back(i*10+j);
      }
      vvi.push_back(vi);
   }
   return vvi;
}

// just for the sample -- print the data sets
std::ostream&
operator<<(std::ostream& os, const Vi& vi)
{
  os << "(";
  std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(os, ", "));
  os << ")";
  return os;
}
std::ostream&
operator<<(std::ostream& os, const Vvi& vvi)
{
  os << "(\n";
  for(Vvi::const_iterator it = vvi.begin();
      it != vvi.end();
      it++) {
      os << "  " << *it << "\n";
  }
  os << ")";
  return os;
}

// recursive algorithm to to produce cart. prod.
// At any given moment, "me" points to some Vi in the middle of the
// input data set. 
//   for int i in *me:
//      add i to current result
//      recurse on next "me"
// 
void cart_product(
    Vvi& rvvi,  // final result
    Vi&  rvi,   // current result 
    Vvi::const_iterator me, // current input
    Vvi::const_iterator end) // final input
{
    if(me == end) {
        // terminal condition of the recursion. We no longer have
        // any input vectors to manipulate. Add the current result (rvi)
        // to the total set of results (rvvvi).
        rvvi.push_back(rvi);
        return;
    }

    // need an easy name for my vector-of-ints
    const Vi& mevi = *me;
    for(Vi::const_iterator it = mevi.begin();
        it != mevi.end();
        it++) {
        // final rvi will look like "a, b, c, ME, d, e, f"
        // At the moment, rvi already has "a, b, c"
        rvi.push_back(*it);  // add ME
        cart_product(rvvi, rvi, me+1, end); add "d, e, f"
        rvi.pop_back(); // clean ME off for next round
    }
}

// sample only, to drive the cart_product routine.
int main() {
  Vvi input(build_input());
  std::cout << input << "\n";

  Vvi output;
  Vi outputTemp;
  cart_product(output, outputTemp, input.begin(), input.end());
  std::cout << output << "\n";
}

Now, I'll show you the recursive iterative version that I shamelessly stole from @John :

The rest of the program is pretty much the same, only showing the cart_product function.

// Seems like you'd want a vector of iterators
// which iterate over your individual vector<int>s.
struct Digits {
    Vi::const_iterator begin;
    Vi::const_iterator end;
    Vi::const_iterator me;
};
typedef std::vector<Digits> Vd;
void cart_product(
    Vvi& out,  // final result
    Vvi& in)  // final result

{
    Vd vd;

    // Start all of the iterators at the beginning.
    for(Vvi::const_iterator it = in.begin();
        it != in.end();
        ++it) {
        Digits d = {(*it).begin(), (*it).end(), (*it).begin()};
        vd.push_back(d);
    }


    while(1) {

        // Construct your first product vector by pulling 
        // out the element of each vector via the iterator.
        Vi result;
        for(Vd::const_iterator it = vd.begin();
            it != vd.end();
            it++) {
            result.push_back(*(it->me));
        }
        out.push_back(result);

        // Increment the rightmost one, and repeat.

        // When you reach the end, reset that one to the beginning and
        // increment the next-to-last one. You can get the "next-to-last"
        // iterator by pulling it out of the neighboring element in your
        // vector of iterators.
        for(Vd::iterator it = vd.begin(); ; ) {
            // okay, I started at the left instead. sue me
            ++(it->me);
            if(it->me == it->end) {
                if(it+1 == vd.end()) {
                    // I'm the last digit, and I'm about to roll
                    return;
                } else {
                    // cascade
                    it->me = it->begin;
                    ++it;
                }
            } else {
                // normal
                break;
            }
        }
    }
}

Cartesian product of several vectors

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;

How to make the cartesian products of vectors, when the number of elements > 1000?

You need to iterate over all combinations of the resulting cartesian product. This is typically achieved by recursion. In each recursion level you then iterate over elements of one input vector.

Here is a sample solution for printing the resulting combinations to std::cout. You can easily modify it for printing to a file by providing an additional reference parameter to an opened std::ofstream object to the recursive function.

#include <iostream>
#include <vector>

template <typename T>
void vector_cartesian_product_helper(
  const std::vector<std::vector<T>>& v, std::vector<T>& combination, size_t level)
{
  if (level == v.size()) {
    for (auto elem : combination)
      std::cout << elem << ";";
    std::cout << "\n";
  }
  else {
    for (const auto& elem : v[level]) {
      combination[level] = elem;
      vector_cartesian_product_helper(v, combination, level + 1);
    }
  }
}

template <typename T>
void vector_cartesian_product(const std::vector<std::vector<T>>& v)
{
  std::vector<T> combination(v.size());
  vector_cartesian_product_helper(v, combination, 0);
}

int main(){
  std::vector<std::vector<int>> test = {{0,1,2,3,4}, {5,6,7}, {8,9,10,11,12,13}};
  vector_cartesian_product(test);
}

Live demo: https://wandbox.org/permlink/PoyEviWGDtEpvN1z

It works with vectors of any sizes and does uses additional memory only of O(N) where N is a number of vectors.

Creating the Cartesian Product of a set of Vectors in Python?

For the specific case of a space of natural numbers, you want np.indices:

>>> np.indices((4, 4)).reshape(2,-1).T
array([[0, 0],
       [0, 1],
       [0, 2],
       [0, 3],
       [1, 0],
       [1, 1],
       [1, 2],
       [1, 3],
       [2, 0],
       [2, 1],
       [2, 2],
       [2, 3],
       [3, 0],
       [3, 1],
       [3, 2],
       [3, 3]])

(numpy actually outputs these in a grid, but you wanted a 1-D list of points, hence the .reshape)

Otherwise, what you're describing is not a powerset but a cartesian product

itertools.product(range(4), repeat=3)

Cartesian Product in c++

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.

TMP: how to generalize a Cartesian Product of Vectors?

Simpler recursive solution. It takes vectors as function arguments, not as a tuple. This version doesn't build temporary tuples, but uses lambdas instead. Now it makes no unnecessary copies/moves and seems to get optimized successfully.

#include<tuple>
#include<vector>

// cross_imp(f, v...) means "do `f` for each element of cartesian product of v..."
template<typename F>
inline void cross_imp(F f) {
    f();
}
template<typename F, typename H, typename... Ts>
inline void cross_imp(F f, std::vector<H> const& h,
                           std::vector<Ts> const&... t) {
    for(H const& he: h)
        cross_imp([&](Ts const&... ts){
                      f(he, ts...);
                  }, t...);
}

template<typename... Ts>
std::vector<std::tuple<Ts...>> cross(std::vector<Ts> const&... in) {
    std::vector<std::tuple<Ts...>> res;
    cross_imp([&](Ts const&... ts){
                  res.emplace_back(ts...);
              }, in...);
    return res;
}

#include<iostream>

int main() {
    std::vector<int> is = {2,5,9};
    std::vector<char const*> cps = {"foo","bar"};
    std::vector<double> ds = {1.5, 3.14, 2.71};
    auto res = cross(is, cps, ds);
    for(auto& a: res) {
        std::cout << '{' << std::get<0>(a) << ',' <<
                            std::get<1>(a) << ',' <<
                            std::get<2>(a) << "}\n";
    }
}

Generate the Cartesian Product of 2 vector<string>s In-Place?

You may try the following approach

#include <iostream>
#include <vector>
#include <string>

int main() 
{
    std::vector<std::string> final{ "a", "b", "c" };
    std::vector<std::string> temp{ "1", "2" };

    auto n = final.size();

    final.resize( final.size() * temp.size() );

    for ( auto i = n, j = final.size(); i != 0; --i )
    {

        for ( auto it = temp.rbegin(); it != temp.rend(); ++it )
        {
            final[--j] = final[i-1] + *it; 
        }

    }

    for ( const auto &s : final ) std::cout << s << ' ';
    std::cout << std::endl;

    return 0;
}

The program output is

a1 a2 b1 b2 c1 c2 

Create a cartesian product of k vectors in R

The cartesian product is implemented in R as outer, or its infix version %o%. Thus:

m %o% m %o% m

# , , 1
# 
#      [,1] [,2]
# [1,]    1    2
# [2,]    2    4
# 
# , , 2
# 
#      [,1] [,2]
# [1,]    2    4
# [2,]    4    8

or in a more easily expandable form,

Reduce(outer, rep(list(m), 3))

which returns the same thing.

---

Related Topics