C++ Program to Implement Next Permutation in STL

Next permutation is an algorithmic operation that rearranges the elements of a range into the next lexicographically greater permutation. In this article, we will learn how to use the next_permutation() function from the Standard Template Library (STL) in C++.

What is Next Permutation?

The Next Permutation is an operation used to generate all the possible permutations an array in lexicographical order. A permutation is the one of N! arrangements of the elements in an array of size N. If the current sequence is the last permutation, the function transforms it into the first one (i.e., sorted in ascending order). It is useful in generating combinations or solving problems related to permutations.

For example, in the code below we have shown the next lexicographical permutation of an integer array:

// Declare an Array
vector<int> nums = {1, 2, 3};

// The Next Permutation of the array will be:
{ 1, 3, 2 }

Using next_permutation Function in STL

The next_permutation() function is defined in the <algorithm> header of STL. It rearranges the range [first, last) into the next lexicographically greater permutation. If such permutation is not possible, it rearranges the sequence into the smallest possible order (sorted in ascending order). Below are some points about this function:

• Header: <algorithm>
• Syntax:

  bool next_permutation(Array Begin Iterator, Array End Iterator);
  

• Return: Returns true if the function could rearrange the object as a lexicographically greater permutation. Otherwise, returns false.

Steps to Implement Next Permutation in C++ STL

Following are steps/algorithm to use next permutation using C++ STL:

• Include the <algorithm> header file.
• Initialize a container like vector or array with the desired elements.
• Call the sort() function to ensure the elements are in ascending order initially.
• Use next_permutation() in a loop to generate and print each permutation.

C++ Program to Implement Next Permutation using STL

The below code is the implementation of the above algorithm in C++ language.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3};
    cout << "Does next permutation possible?: ";
    cout << next_permutation(nums.begin(), nums.end()) << endl;
    cout << "Next Permutation of the Input Array: ";
    for (int num : nums) {
            cout << num << " ";
    }
    cout<< endl;

    // Sort initially to get first permutation
    sort(nums.begin(), nums.end());

    cout << "All permutations:" << endl;
    do {
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end()));

    return 0;
}

The output of above code will be

Does next permutation possible?: 1
Next Permutation of the Input Array: 1 3 2 
All permutations:
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

Time and Space Complexity

Time Complexity:

• next_permutation(): O(n), where n is the number of elements in the container.
• Generating all permutations: O(n × n!) for n elements.

Space Complexity: O(1) extra space as next_permutation works in-place.