C++ Reference ยท Algorithms
The std::next_permutation and std::prev_permutation algorithms
Reference for C++ next_permutation, prev_permutation and is_permutation: step through all orderings of a range in lexicographic order, with duplicates handled.
std::next_permutation rearranges a range into the next greater ordering in lexicographic (dictionary) order and returns true. If the range is already the greatest ordering (sorted descending), it rearranges it into the smallest (sorted ascending) and returns false. std::prev_permutation goes the opposite way. std::is_permutation checks whether two ranges contain the same elements, ignoring order.
To visit every permutation exactly once, sort the range first and loop with do { ... } while (std::next_permutation(...)). Duplicate values do not cause repeated permutations: for {1, 1, 2} there are only 3 distinct arrangements.
std::sort(v.begin(), v.end()); do { /* use v */ } while (std::next_permutation(v.begin(), v.end()));
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class BidirIt> bool next_permutation(BidirIt first, BidirIt last); template<class BidirIt, class Compare> bool next_permutation(BidirIt first, BidirIt last, Compare comp); template<class BidirIt> bool prev_permutation(BidirIt first, BidirIt last); // and a Compare overload template<class FwdIt1, class FwdIt2> bool is_permutation(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);
| Name | Description |
|---|---|
first, last |
The range to permute in place. |
comp |
Ordering that defines what "greater" means (default <). |
first2, last2 |
The second range for is_permutation. |
Returns: next_permutation returns true if a greater arrangement was produced, false if the range wrapped around to the smallest one. prev_permutation is the mirror image. is_permutation returns a bool.
Errors / undefined behavior: none for valid ranges, but the loop depends on the starting arrangement (see below).
Usage notes
- Sort first to enumerate everything. Starting from an unsorted arrangement visits only the permutations that come after it, and then stops when the wrap-around returns
false. - Count grows factorially: n distinct elements have n! permutations (10 elements: 3,628,800). Loops above n = 10 or 11 are too slow for the 5 s run limit of our runner.
- Duplicates are skipped automatically, so the count is n! divided by the product of the factorials of the repeat counts.
- Complexity: each call is O(n) in the worst case, but the average amortized cost over the full sequence is O(1) swaps per step.
- Same comparator for the whole run. A descending order loop uses
std::greaterin both the sort and everynext_permutationcall. - Combinations: the standard library has no combinations function. A common trick is permuting a vector of 0/1 flags (
1 1 0 0) to select subsets. - Not random: for a random arrangement use
std::shuffle. is_permutationis O(nยฒ) in the worst case when the ranges are not sorted. Sort copies and useequalfor large inputs.