std::next_permutation and prev_permutation in C++

For a given collection of N elements, a permutation is N! (factorial) possible arrangements the elements. Different permutations can be ordered according to how they compare lexicographically to each other.

In C++, the std::next_permutation() and std::prev_permutation() functions are used to rearrange the elements of container in lexicographically larger and smaller permutation of the given range respectively. They are defined inside the <algorithm> header file.

In this article, we will learn how to use the next_permuatation() and prev_permutation() in C++

std::next_permutation()

The std::next_permutation in C++ is used to rearrange the elements of the given range [first, last) to the lexicographical larger permutation if it exists.

Syntax

std::next_permutation(first, last);

Parameters

• first: Iterator to the first element of the given range.
• last: Iterator to the theoretical element just after the last element of the given range.

Return Value

• Returns true if the container could be rearranged to the to the lexicographical larger permutation.
• Returns false otherwise.

Example of std::next_permutation()

// C++ program to demonstate the use of // std::next_permutation() function #include <bits/stdc++.h> using namespace std; int main() {  vector<int> v = {1, 2, 3};    // Printing all the greater permutations  // of the current vector  do {  for (auto i: v) cout << i << " ";  cout << endl;  } while (next_permutation(v.begin(), v.end()));  return 0; } 

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 

Time Complexity: O(n), for each permutation where n is the number of elements in the range.
Auxiliary Space: O(1)

Explanation: The total number of permutations of vector of 3 elements is 3! = 6. We already took the smallest possible permutation as the starting point, so we were able to print all the permutations using next_permutation().

std::prev_permutation()

The std::prev_permutation is used to rearrange the elements of the given range [first, last) in the lexicographical smaller permutation if it exists.

Syntax

std::prev_permutataion(first, last)

Parameters

• first: Iterator to the first element of the given range.
• last: Iterator to the theoretical element just after the last element of the given range.

Return Value

• Returns true if the container could be rearranged to the to the lexicographical smaller permutation.
• Returns false otherwise.

Example of std::prev_permutation()

// C++ program to demonstate the use of // std::next_permutation() function #include <bits/stdc++.h> using namespace std; int main() {  vector<int> v = {2, 1, 3};    // Printing all the possible permutations // smaller than the current one  do {  for (auto i: v) cout << i << " ";  cout << endl;  } while (prev_permutation(v.begin(), v.end()));  return 0; } 

2 1 3 1 3 2 1 2 3 

Time Complexity: O(n), for each permutation where n is the number of elements in the range.
Auxiliary Space: O(1)

Explanation: The total number of permutations of vector of 3 elements is 3! = 6. But we were only able to print 3 permutations because we didn't took the largest permutation as starting point for prev_permutation() function. So, all the permutation greater than the permutation {2, 1, 3} are left out.