Next permutation as n-choose-r (tools/next_permutation.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-06-13 13:30:25+09:00
• Include: #include "tools/next_permutation.hpp"

template <typename Iterator>
bool next_permutation(Iterator first, Iterator k, Iterator last);

It generates the next permutation as n-choose-r. It returns true if the next permutation exists, false otherwise.

Usage

// 9-choose-3
int k = 3;
do {
  std::cout << std::string(s.begin(), std::next(s.begin(), k)) << std::endl;
} while (tools::next_permutation(s.begin(), std::next(s.begin(), k), s.end()));

Constraints

• first $\leq$ k $\leq$ last

Time Complexity

• $O(\text{last} - \text{first})$

License

• CC0

Author

• anqooqie

Code

#ifndef TOOLS_NEXT_PERMUTATION_HPP
#define TOOLS_NEXT_PERMUTATION_HPP

#include <algorithm>

namespace tools {

  template <typename Iterator>
  bool next_permutation(const Iterator first, const Iterator k, const Iterator last) {
    ::std::reverse(k, last);
    return ::std::next_permutation(first, last);
  }
}

#endif

#line 1 "tools/next_permutation.hpp"



#include <algorithm>

namespace tools {

  template <typename Iterator>
  bool next_permutation(const Iterator first, const Iterator k, const Iterator last) {
    ::std::reverse(k, last);
    return ::std::next_permutation(first, last);
  }
}

Back to top page