×

# std::next_permutation() function with example in C++ STL

In this article, we are going to see what is the STL function next_permutation() and what's the use of it and how to use it in a program?
Submitted by Radib Kar, on August 03, 2020

## std::next_permutation()

next_permutation() is an STL function that finds the next lexicographical permutation for a given permutation.

A Permutation is a particular arrangement for a given set of numbers. Say, we have a set with n numbers where n! permutations are possible. For example, if the set of numbers are {1, 2, 3} then,

The permutations ordered in lexicographical order will be,

Permutation 1: 1, 2, 3
Permutation 2: 1, 3, 2
Permutation 3: 2, 1, 3
Permutation 4: 2, 3, 1
Permutation 5: 3, 1, 2
Permutation 6: 3, 2, 1

The above are six permutations that can be generated from the above-mentioned example set. Also, the permutations are lexicographically ordered which means the next permutation of permutation 1 is permutation 2 and permutation 6 has no next permutation since that's the highest one.

## Syntax

The STL function next_permutation() helps us to find the next permutation for a given permutation. Below is the syntax for next_permutation()

```bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last
);
```

## Parameter(s)

• BidirectionalIterator first - starting iterator to the permutation sequence
• BidirectionalIterator last - ending iterator to the permutation sequence

## Return value

Return type: bool

Returns true if it finds the next permutation and changes the current permutation sequence in place to the next permutation sequence. Returns false, if no next permutation is found.

## Example and Usage

Below is the example program where we have used the above STL function to compute next permutation.

### Find the next permutation

In the below program we will find the next permutation using the STL function just discussed above.

```#include <bits/stdc++.h>
using namespace std;

void print(vector<int>& nums)
{
for (auto it : nums)
cout << it << " ";
cout << endl;
}

int main()
{
cout << "Enter number of elements in the permutation\n";
int n;
cin >> n;

cout << "Input the permutations\n";
vector<int> nums(n);
for (int i = 0; i < n; i++)
cin >> nums[i];

//next_permutation returns true if it's
//able to find the next permutation
//changes the permutation in place to the
//next permutation
if (next_permutation(nums.begin(), nums.end())) {
cout << "The next permutation is:\n";
print(nums);
}
else
cout << "No next permutation found\n";

return 0;
}
```

#### Output

```Enter number of elements in the permutation
3
Input the permutations
2 1 3
The next permutation is:
2 3 1
```

### Find all permutations lexicographically

We can also find all permutations lexicographically by using next_permutation(). For example, all the permutations for n=3 in lexicographical order will be

Permutation 1: 1, 2, 3
Permutation 2: 1, 3, 2
Permutation 3: 2, 1, 3
Permutation 4: 2, 3, 1
Permutation 5: 3, 1, 2
Permutation 6: 3, 2, 1

```#include <bits/stdc++.h>
using namespace std;

void print(vector<int>& nums)
{
for (auto it : nums)
cout << it << " ";
cout << endl;
}

int main()
{
cout << "Enter number of elements in the permutation\n";
int n;
cin >> n;

//first permutation is 1,2,3,4...,n
vector<int> nums(n);
for (int i = 0; i < n; i++)
nums[i] = i + 1;

int count = 1;

//the while loop will break when no more
//next Permutation is possible
//as the function next_permutation will
//return false then
do {
cout << "Permutation " << count++ << endl;
print(nums);
} //in places converts to next permutation if there exists the next permutation
while (next_permutation(nums.begin(), nums.end()));

return 0;
}
```

#### Output

```Enter number of elements in the permutation
3
Permutation 1
1 2 3
Permutation 2
1 3 2
Permutation 3
2 1 3
Permutation 4
2 3 1
Permutation 5
3 1 2
Permutation 6
3 2 1
```

The above next_permutation() compares based on the '>' operator whereas we can extend the syntax by adding user-defined comparator function to work on user-defined objects too.

```bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last,
Comparator comp);
```