nPr_iterative

npr_iterative.cpp

#include <iostream>
#include <unordered_set>
#include <vector>

template <typename T>
std::vector<std::vector<T>> permute(std::vector<T> vec, int r) {
  using PermTy = std::pair<std::unordered_set<int>, std::vector<T>>;

  std::vector<PermTy> permutations{{}};
  while (r-- > 0) {
    std::vector<PermTy> npermutations;

    for (int i = 0; i < static_cast<int>(vec.size()); ++i)
      for (auto [perm_set, perm_vec] : permutations)
        if (!perm_set.count(i))
          perm_set.emplace(i), perm_vec.emplace_back(vec[i]),
              npermutations.emplace_back(perm_set, perm_vec);

    permutations = std::move(npermutations);
  }

  std::vector<std::vector<T>> ret;
  for (auto &&[_, perm] : permutations)
    ret.push_back(perm);

  return ret;
}

int main() {
  for (auto &perm : permute<std::string>({"how", "are", "you"}, 2)) {
    for (auto &v : perm)
      std::cout << v << " ";
    std::cout << "\n";
  }
}