cartesian product c++

cartesian_product.cpp

#include <iostream>
#include <deque>

template<typename T>
std::deque< std::deque<T> >&&
cartesian_product(std::deque< std::deque<T> > &bags) {
  std::deque< std::deque<T> > output{std::deque<T>{}};

  if (!bags.size())
    return std::move(output);

  std::deque<T> first{bags[0]};
  std::deque< std::deque<T> > rest{bags.begin() + 1, bags.end()};

  for (auto item : first) {
    for (auto bag : cartesian_product(rest)) {
      bag.push_front(item);
      output.push_back(bag);
    }
  }

  return std::move(output);
}

void print(std::deque< std::deque<int> >& bags) {
  std::cout << "[" << std::endl;
  for (auto permutation : bags) {
    std::cout << "\t[ ";
    for (auto item : permutation) {
      std::cout << item << " ";
    }
    std::cout << "]" << std::endl;
  }
  std::cout << "]" << std::endl;
}

int main() {
  std::deque<int> first_bag;
  for (int i = 1; i < 4; ++i)
    first_bag.push_back(i);

  std::deque<int> second_bag;
  for (int i = 4; i < 6; ++i)
    second_bag.push_back(i);

  std::deque<int> third_bag;
  for (int i = 6; i < 10; ++i)
    third_bag.push_back(i);

  std::deque< std::deque<int> > bags;

  bags.push_back(first_bag);
  bags.push_back(second_bag);
  bags.push_back(third_bag);

  std::cout << "input bags:" << std::endl;
  print(bags);

  std::deque< std::deque<int> > result{cartesian_product(bags)};

  std::cout << "\ncartesian product:" << std::endl;
  print(result);
}