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.

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
    );

Parameters:

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

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.

1) 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

2) 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);