Next Permutation c++ | FlutterTPoint

The Next Permutation in c++ algorithm is used to generate the lexicographically next permutation of a sequence of elements. It rearranges the elements into the next lexicographically greater permutation, allowing us to iterate over all possible permutations of a sequence.

Here’s an example implementation of the Next Permutation algorithm in C++:


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

void nextPermutation(std::vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;

    // Find the first decreasing element from the right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        // Find the next greater element than nums[i] from the right
        int j = n - 1;
        while (j > i && nums[j] <= nums[i]) {
            j--;
        }
        // Swap the elements at positions i and j
        std::swap(nums[i], nums[j]);
    }

    // Reverse the sequence from i+1 to the end
    std::reverse(nums.begin() + i + 1, nums.end());
}

Let’s go through the code step by step:

The function nextPermutation takes a reference to a vector of integers nums as input.
We initialize a variable n with the size of the vector nums and a variable i with n - 2. The index i represents the element from the right that is the first decreasing element in the sequence.
We enter a while loop to find the first decreasing element from the right. The loop continues until i becomes less than 0 or the element at index i is less than the element at index i + 1.
If we found a decreasing element (i.e., i is greater than or equal to 0), we proceed to find the next greater element than nums[i] from the right.
We initialize a variable j with n - 1 and enter another while loop. The loop continues until j becomes greater than i or the element at index j is greater than nums[i].
Once we find the next greater element at index j, we swap the elements at positions i and j.
After the swap, we need to make sure that the remaining part of the sequence after position i is in ascending order. To achieve this, we reverse the sequence from index i + 1 to the end using the std::reverse function from the <algorithm> library.

That’s it! After calling the nextPermutation function, the vector nums will be modified to contain the lexicographically next permutation.

Here’s an example usage of the `Next Permutation` function:


int main() {
    std::vector<int> nums = {1, 2, 3};
    nextPermutation(nums);

    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

The output of this code will be: