Cartesian for-each at runtime

Useful when the number of arguments to a Cartesian product is determined at runtime.

Cartesian product

In mathematics, the Cartesian product of two sets \(A\) and \(B\) is the set: \[A\times B := \{(x,y) : x \in A,\ y \in B\}\] For two C++ vectors, \(\{0,1,2\}\) and \(\{3,4\}\), the product is a vector of two-tuples: \(\{(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)\}\). The product of \(n\) vectors is easy to generate with nested for loops or template meta-programming, as long as \(n\) is known at compile time.

Cartesian product at runtime

Sometimes \(n\) is only known at runtime. If we knew its maximum, we could still pre-generate a function for each value of \(n\) via template meta-programming, but here we generate the product dynamically instead. We keep to vectors for simplicity; the scheme applies to other ‘vector-like’ types too.

Breadth-first algorithm (pseudo-code)

The breadth-first algorithm is straightforward to think of.

// procedure: extend_cp
// input: cps, es
// output: cps extended

result <- {}
for p in cps
  for e in es
    p_ <- p
    p_.append(e)
    result.append(p_)
return result

// procedure: cartProdBf
// input: vov vector<vector<T>> vector of vectors (for eg.)
// output: vov_ vector<vector<T>> cart prod result
if vov.empty
  return {}

//
// <| front |>
//  |   .   | . | . | . . . | . | (vov)
//          |<      tail       >|
//
init <- {{e} for e in vov.front} // cart prod seed

// see https://en.cppreference.com/w/cpp/algorithm/accumulate
return accumulate(vov.tail, init, extend_cp)

Better approach: depth-first algorithm

The breadth-first algorithm materializes every member of the product at once. Better to generate one member at a time and act on it (say, call a function on it). This depth-first algorithm does that with while loops and iterator arithmetic. I borrowed it from my colleague Andrey Asadchev’s work in TiledArray.

//
// filename: cartesian_foreach.hpp
//
// required headers:
//   - vector
//   - utility
//   - functional

template <typename R, typename F>
void cartesian_foreach(std::vector<R> const& rs, F&& call_back) {
  using It = decltype(std::begin(rs[0]));
  using T = typename R::value_type;

  if (rs.empty()) return;

  // a Cartesian product with an empty factor is empty
  for (auto&& r : rs)
    if (std::begin(r) == std::end(r)) return;

  std::vector<It> its, ends;
  its.reserve(rs.size());
  ends.reserve(rs.size());

  for (auto&& r : rs) {
    its.push_back(std::begin(r));
    ends.push_back(std::end(r));
  }

  while (its.front() != ends.front()) {
    std::vector<T> p;
    p.reserve(its.size());

    for (auto&& it: its)
      p.push_back(*it);

    // do something with the cartesian product
    std::invoke(std::forward<F>(call_back), p);

    size_t i = its.size();
    while (i > 0) {
      --i;
      ++its[i];
      if (i == 0) break;
      if (its[i] != ends[i]) break;
      its[i] = std::begin(rs[i]);
    }
  }
}

Example use

//
// file name: main.cpp
//
// required headers:
//   - cartesian_foreach.hpp
//   - vector
//   - iterator
//   - iostream

// prints a vector of printables
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> const& vec) {
  os << "{";
  if (!vec.empty()) {
    os << vec.front();
    for (auto it = std::next(vec.begin()); it != vec.end(); ++it)
      os << ", " << *it;
  }
  os << "}";
  return os;
}

//
// main function
//
int main() {
  using std::cout;
  using std::endl;

  auto vov = std::vector<std::vector<int>>{{1, 2}, {3, 4}, {5, 6}};

  auto print_vec = [](auto const& v) {
    cout << v << endl;
  };

  cartesian_foreach(vov, print_vec);

  cartesian_foreach(decltype(vov){}, print_vec); // empty vov, no output

  return 0;
}

Output:

{1, 3, 5}
{1, 3, 6}
{1, 4, 5}
{1, 4, 6}
{2, 3, 5}
{2, 3, 6}
{2, 4, 5}
{2, 4, 6}