Find the Next Permutation in C++

Last Updated on May 10, 2023 by Prepbytes

A permutation is defined as each of the numerous possible arrangements or orders that can be made for a set of objects or a group of objects. N! is used to represent it, where N is the range’s total number of elements. So, in this article, we will be discussing the next permutation in C++.

What is the Next Permutation?

The next lexicographically superior permutation of an integer in an array is that integer’s next permutation. In more formal terms, if all of the array’s permutations are sorted in one container according to their lexicographical order, the permutation that follows it in the sorted container is the next permutation of that array. If this is not possible, the array must be rearranged in the smallest possible order (sorted ascending).

As a result, there are two ways to solve this problem:

1. using in-built functions
2. without using in-built functions

So, let us discuss each of the methods to find the next permutation.

Method 1: Using in-built functions

The C++ algorithm’s next_permutation() function is used to reorder the elements in the range [first, last] into the next lexicographically greater permutation.

Elements are compared with the operator in the first version and the given binary comparison function comp in the second.

Parameters Included

There are three parameters to the next_permutation() function:

1. The first step is to create a bidirectional iterator that points to the first element in the range to be permuted.
2. Finally, an input iterator pointing one position beyond the range to be permuted is provided.
3. comp is a binary predicate function that takes two arguments and returns true if they are in the correct order; otherwise, it returns false. The elements are ordered using strict weak ordering.

Return Value of the Next Permutation Function

If the function is able to reorder the object into lexicographically greater permutations, it returns true. Otherwise, the function returns false, indicating that the arrangement is not greater than the previous one, but rather the smallest possible (sorted in ascending order).

Time Complexity of the Next Permutation Function

For half the distance between first and last, the time complexity reaches linear.

Code Implementation for Finding the Next Permutation

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3}; // example array
    std::next_permutation(nums.begin(), nums.end()); // find the next permutation

    // print the next permutation
    for (int num : nums) {
        std::cout << num << " ";
    }
    // expected output: 1 3 2 

    return 0;
}

Output :

1 3 2

Method 2: Without using in-built function

In C++, we can also use our own permutation function to find the next permutation. Let’s talk about the C++ implementation.

Code Implementation for Finding the Next Permutation

#include <iostream>
#include <vector>

void reverse(std::vector<int>& nums, int start, int end) {
    while (start < end) {
        std::swap(nums[start], nums[end]);
        start++;
        end--;
    }
}

void nextPermutation(std::vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i+1]) {
        i--;
    }
    if (i >= 0) {
        int j = n - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        std::swap(nums[i], nums[j]);
    }
    reverse(nums, i+1, n-1);
}

int main() {
    std::vector<int> nums = {1, 2, 3}; // example array
    nextPermutation(nums); // find the next permutation

    // print the next permutation
    for (int num : nums) {
        std::cout << num << " ";
    }
    // expected output: 1 3 2 

    return 0;
}

Output

1 3 2

In this case, two helper functions are defined: reverse and nextPermutation.

• The reverse function takes a vector of integer nums and two indices start and end. It reorders the elements in the subarray nums[start…end].
• The nextPermutation function computes the next permutation in place given a vector of integer nums. It works as follows:
  • Find the largest index i for which nums[i] = nums[i+1].
  • If no such index exists, the array is already in descending order, and the next permutation cannot be computed.
  • Calculate the largest index j such that nums[j] > nums[i]. Swap nums[i] and nums[j].
  • Reverse the order of the elements from nums[i+1] to the end of the array.

Conclusion
The following article explains how to find the next permutation in C++. The next permutation is the lexicographically next arrangement of a set of objects, and there are two ways to find it: with and without built-in functions. The built-in function next_permutation() from the C++ algorithm library is discussed, as well as its parameters and return values. The next_permutation() function’s time complexity is also discussed. There is also a C++ implementation of finding the next permutation without using built-in functions, which involves defining two helper functions and working through a series of steps to compute the next permutation.

Frequently Asked Questions (FAQs)

Q1. In C++, how do you determine the next permutation?
Ans. The C++ algorithm’s next_permutation() function reorders the elements in the range [first, last) into the next lexicographically greater permutation.

Q2. What is the next 123 permutation?
Ans. For instance, if the given array is nums = [1,2,3], the number formed by combining its elements is 123. The following number with the same digits as 123 is 132. Therefore, the output will be nums = [1,3,2] .

Q3. What’s the next possible permutation?
Ans. The following permutation is the largest number. For example, if an array has arr = 1, 2, 3, 6, 5, 4, the number is 123654. Because the next greater element is 124356, return the array 1, 2, 4, 3, 5, 6.

Q4. What is the complexity of the next permutation in C++?
Ans. In the worst case, the complexity of std::next_permutation, which transforms the permutation to the next permutation in the lexicographic order, is O(n).

Q5. What is the next lexicographic permutation in C++?
Ans. The lexicographically next permutation is essentially the greater permutation.