permutation.cc

#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace yuuki {
namespace detail {
static const constexpr size_t __bsearch_thrd = 16;
template <typename RandAccIter, typename BinaryPred>
RandAccIter bsearch_last_comp(RandAccIter first,
                              RandAccIter last,
                              RandAccIter target,
                               BinaryPred comp) {
  RandAccIter saved = last;
  while (first < last) {
    RandAccIter mid = first + std::distance(first, last) / 2;
    if (not comp(*target, *mid)) {
      last = mid;
    } else if (std::next(mid) != last and comp(*target, *std::next(mid))) {
      first = std::next(mid);
    } else {
      return mid;
    }
  }
  return saved;
}

template <typename BidirIter, typename BinaryPred>
bool do_permutation(BidirIter first, BidirIter last, BinaryPred comp) {
  using category = typename std::iterator_traits<BidirIter>::iterator_category;
  static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::value,
      "bidirectional_iterator required!");
  static constexpr const
  bool is_rndacc = std::is_base_of<std::random_access_iterator_tag, category>::value;
  if (first == last or std::next(first) == last) {
    return false;
  } else /* lbi */;
  BidirIter i = std::prev(last);
  while (true) {
    BidirIter ii = i;
    --i;
    if (comp(*i, *ii)) {
      BidirIter j = last;
      if (is_rndacc and std::distance(ii, last) > __bsearch_thrd) {
        j = bsearch_last_comp(ii, last, i, comp);
      } else {
        do {
          --j;
        } while (not comp(*i, *j));
      }
      std::iter_swap(i, j);
      std::reverse(ii, last);
      return true;
    }
    if (i == first) {
      return false;
    }
  }
}
}  // namespace detail

template <typename BidirIter,
          typename BinaryPred = std::less<typename std::iterator_traits<BidirIter>::value_type>>
bool prev_permutation(BidirIter first, BidirIter last, BinaryPred binpred = BinaryPred()) {
  using namespace std::placeholders;
  return detail::do_permutation(first, last, std::bind(binpred, _2, _1));
}

template <typename BidirIter,
          typename BinaryPred = std::less<typename std::iterator_traits<BidirIter>::value_type>>
bool next_permutation(BidirIter first, BidirIter last, BinaryPred binpred = BinaryPred()) {
  return detail::do_permutation(first, last, binpred);
}
}  // namespace yuuki

int main() {
  std::string s = "1234";
  std::cout << "Please input a stream that you want to do permutation: ";
  std::cin >> s;
  std::cout << s << '\n';
  while (yuuki::next_permutation(s.begin(), s.end())) {
    std::cout << s << '\n';
  }
  std::cout << "----------\n";
  std::cout << s << '\n';
  while (yuuki::prev_permutation(s.begin(), s.end())) {
    std::cout << s << '\n';
  }
  std::cout << std::flush;
  return 0;
}