Skip to content
Tutorials Center
My learning

Topics

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.

C++
std::sort(v.begin(), v.end());
do { /* use v */ } while (std::next_permutation(v.begin(), v.end()));

Try it

C++ All permutations of three letters

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.

C++ Duplicates, return values and is_permutation

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

C++
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::greater in both the sort and every next_permutation call.
  • 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_permutation is O(nยฒ) in the worst case when the ranges are not sorted. Sort copies and use equal for large inputs.