#include <iostream>
#include <vector>
#include <cassert>

void permute_impl(size_t width, std::vector<std::vector<int>> const &mat,
                  size_t column, std::vector<int> &prefix) {
  if (column < width) {
    for (auto &row : mat) {
      prefix.push_back(row[column]);
      permute_impl(width, mat, column + 1, prefix);
      prefix.pop_back();
    }
  } else {
    for (auto i : prefix)
      std::cout << i << ' ';
    std::cout << '\n';
  }
}

void permute(std::vector<std::vector<int>> const &mat) {
  if (mat.empty())
    return;
  std::vector<int> prefix;
  size_t N = mat[0].size();
  // assert that all rows are the same size
  for (auto &row : mat)
    assert(row.size() == N);
  permute_impl(N, mat, 0, prefix);
}

int main() {
  std::vector<std::vector<int>> mat = {
      {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
  };

  permute(mat);
}