Next Permutation in C++

Method 1: Next Permutation Using in-built functions

Algorithm

1. Use the next_permutation function from the <algorithm> library.
2. Pass the iterators representing the range of elements to permute.
3. Check if next_permutation returns true.
4. If true, print the next permutation.

Implementation

• C++

C++

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

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

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

    if (std::next_permutation(nums.begin(), nums.end())) {
        std::cout << "Next Permutation: ";
        for (int num : nums) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "No next permutation exists." << std::endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Original Sequence: 1 2 3 
Next Permutation: 1 3 2 

Explanation

• We initialize a vector nums with elements {1, 2, 3}.
• We use next_permutation(nums.begin(), nums.end()) to generate the next permutation.
• If next_permutation returns true, we print the next permutation; otherwise, we indicate that no next permutation exists.

Method 2: Next Permutation Without using in-built function

Algorithm

1. Find the largest index i such that nums[i] < nums[i+1].
2. If no such index exists, the sequence is the last permutation; reverse the entire sequence.
3. Otherwise, find the largest index j such that nums[j] > nums[i].
4. Swap nums[i] with nums[j].
5. Reverse the sub-array from nums[i+1] to the end.

Implementation

• C++

C++

#include <iostream>
#include <vector>

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

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

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

    nextPermutation(nums);

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

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Original Sequence: 1 2 3 
Next Permutation: 1 3 2 

Explanation

• We define a function nextPermutation to compute the next permutation of a sequence.
• We use the logic described in the algorithm to find the next permutation.
• We call nextPermutation(nums) to update the nums vector to its next permutation.

Frequently Asked Questions

What is the next permutation formula in C++?

In C++, the next permutation is computed using the std::next_permutation function from the <algorithm> library, which rearranges elements in a sequence to generate the lexicographically next greater permutation.

What is the Nextperm function?

The next_permutation function in C++ is a part of the <algorithm> library. It rearranges elements in a sequence to produce the lexicographically next greater permutation, returning true if a next permutation exists and false otherwise.

How to get the next permutation?

To get the next permutation in C++, use the std::next_permutation function from the <algorithm> library. Pass iterators representing the range of elements to permute, and the function will rearrange the elements to their next lexicographically greater permutation if it exists.

What is an example of a next permutation?

An example of a next permutation in C++ is when given the sequence {1, 2, 3}, calling std::next_permutation would rearrange it to {1, 3, 2}, which is the lexicographically next greater permutation.

Conclusion

This article taught us how to find the next permutation in C++. The Next Permutation algorithm in C++ serves as a powerful tool for generating permutations in lexicographic order. Whether utilizing in-built functions or implementing custom solutions, mastering this algorithm empowers programmers to efficiently solve various problems, from combinatorial challenges to algorithmic puzzles.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the pattern followed.

Now, we recommend you practice problem sets based on this to master your fundamentals. You can get a wide range of questions similar to this here.