Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Next Permutation?
2.1.
Syntax
2.2.
Parameters
2.3.
Return Value
3.
Method 1: Next Permutation Using in-built functions
3.1.
Algorithm
3.2.
Implementation
3.3.
C++
3.4.
 
4.
Method 2: Next Permutation Without using in-built function
4.1.
Algorithm
4.2.
Implementation
4.3.
C++
4.4.
 
5.
Frequently Asked Questions
5.1.
What is the next permutation formula in C++?
5.2.
What is the Nextperm function?
5.3.
How to get the next permutation?
5.4.
What is an example of a next permutation?
6.
Conclusion
Last Updated: May 12, 2024
Easy

Next Permutation in C++

Author Urwashi Priya
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In combinatorial mathematics and algorithm design, permutations play a pivotal role. They represent the rearrangement of elements in a sequence, offering insights into various problem-solving scenarios. Among these permutations, understanding the concept of the "next permutation" holds particular significance in algorithms and programming.

Next Permutation in C++

What is the Next Permutation?

The Next Permutation algorithm generates the lexicographically next greater permutation of a sequence. It rearranges the elements in the sequence into the next greater order, considering the dictionary or lexicographic ordering of the elements.

In simpler terms, given a sequence of elements, the Next Permutation algorithm rearranges these elements to produce the next permutation in lexicographic order. This is crucial in scenarios where permutations need to be generated systematically or when finding the next arrangement is essential for optimization or solving certain problems efficiently.

Syntax

The syntax for the Next Permutation algorithm in C++ is:

template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

The next_permutation function in C++ takes two iterators representing the range of elements to permute. It rearranges the elements in this range to their next lexicographically greater permutation if such a permutation exists. The function returns true if a next permutation was found, otherwise false.

Parameters

  • first: Iterator pointing to the beginning of the sequence or range of elements.
  • last: Iterator pointing to the end of the sequence or range of elements.

The first and last parameters define the range of elements for which the next permutation needs to be computed. The first iterator points to the first element in the sequence, while the last iterator points to one position past the last element in the sequence. The range between first and last will be modified to contain the next lexicographically greater permutation if it exists.

Return Value

The next_permutation function returns a boolean value:

  • true if the function successfully finds the next lexicographically greater permutation.
  • false if the current sequence is already the last permutation, and no next permutation exists.

The return value of next_permutation indicates whether a next permutation was found. If a next permutation exists, the function rearranges the elements and returns true. If the current permutation is already the last one in lexicographic order, the function leaves the elements unchanged and returns false.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

 

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

 

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

Previous article
Next Permutation
Next article
Single Number
Live masterclass