1. Introduction to C++: A Comprehensive Guide with Code Examples - 2023
2. Mastering Data Types in C++: A Comprehensive Guide with Codes and Examples (2023)
3. Learn About Variables and Types of Variables in C++ | Codzify.com
4. Control Statements in C++: A Comprehensive Guide for 2023
5. C++ Tutorial: Understanding Switch Statements with Codes and Examples in 2023
6. Understanding Memory Allocation and Pointers in C++: A Beginners Guide
7. Functions in C++
8. Call by value and Call by Reference in C++ in depth
9. Array in C++
10. 2d arrays in C++
11. Classes and Objects in C++
12. Static Functions in C++
13. Constructors and Destructors in C++ - A Complete Guide with Examples
14. Mastering Copy Constructor in C++ - Shallow vs Deep Copy with Examples | Codzify
15. Understanding Friend Functions in C++ Made Simple!
16. Inline Functions in C++
17. this Pointer in C++
18. Mastering Inheritance in C++: Types and Examples Explained
19. Types of Inheritance in C++
20. Polymorphism in C++ Explained with Codes and Examples in 2023
21. Templates in C++
22. Getting the Value of a MultiMap in C++: Step-by-Step Guide with Examples
23. Multimap Find and Replace Operator in C++: Step-by-Step Guide - Codzify Topics
24. Exploring the Next_Permutation Algorithm without STL in C++ - Codzify Topics
25. C++ - The Difference Between Map and HashMap in STL
26. Updating Values in a std::multimap in C++ - Codzify Topics
27. Which data structure sorts the elements on insertion in C++ STL?
28. Can we implement Red Black Tree in c++ by STL containers?
29. How to Dynamically Declare an Array of Objects with a Constructor in C++ - A Step-by-Step Guide
30. What is the difference between a pointer and an object in C++?
31. Mastering Red-Black Trees with STLs Internal Implementation: A Step-by-Step Guide

**Article by:** Manish Methani

**Last Updated:** September 8, 2021 at 10:04am IST

Permutations are a fundamental concept in combinatorial mathematics and computer science. They represent the rearrangement of elements in a sequence, creating unique orders of those elements. In C++, the Standard Template Library (STL) provides a handy `next_permutation`

function for generating permutations. But have you ever wondered how to implement this function from scratch, without relying on the STL? In this comprehensive guide, we'll explore the best algorithm to implement the `next_permutation`

function in C++ step by step, providing you with a deep understanding of the process.

Permutations are essential in various programming challenges, such as generating combinations, solving puzzles, and optimizing algorithms. The `next_permutation`

function is a powerful tool to efficiently produce permutations of a sequence. In this guide, we'll delve into the inner workings of this function and implement it from the ground up.

Before we dive into the implementation, let's establish a fundamental understanding of permutations. A permutation of a sequence is an arrangement of its elements in a specific order. Given a sequence, we aim to generate the next lexicographically larger permutation.

The `next_permutation`

algorithm follows a specific sequence of steps to transform the current permutation into the next one. Understanding these steps is crucial for implementing the function without relying on STL.

We'll break down the implementation into detailed steps, ensuring that you grasp each part of the algorithm. These steps include finding the longest suffix with non-increasing order, identifying the first element to swap, locating the smallest element in the suffix, swapping the elements, and reversing the suffix.

To solidify your understanding, here's an example code demonstrating the implementation of the `next_permutation`

algorithm in C++:

#include <iostream> #include <algorithm> // Include the algorithm header #include <vector> // Function to find the next permutation bool nextPermutation(std::vector& sequence) { int n = sequence.size(); int i = n - 2; while (i >= 0 && sequence[i] >= sequence[i + 1]) { i--; } if (i < 0) { return false; // No more permutations } int j = n - 1; while (sequence[j] <= sequence[i]) { j--; } std::swap(sequence[i], sequence[j]); std::reverse(sequence.begin() + i + 1, sequence.end()); return true; // Next permutation found } int main() { std::vector sequence = {1, 2, 3}; std::cout << "Original sequence: "; for (int val : sequence) { std::cout << val << " "; } std::cout << std::endl; std::cout << "All permutations: " << std::endl; do { for (int val : sequence) { std::cout << val << " "; } std::cout << std::endl; } while (nextPermutation(sequence)); return 0; }

Original sequence: 1 2 3 All permutations: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

The first step of the algorithm is to identify the longest suffix with non-increasing order in the sequence. This suffix represents the portion of the sequence that does not need to be modified to generate the next permutation.

In the code, this step is implemented as follows:

int n = sequence.size(); int i = n - 2; while (i >= 0 && sequence[i] >= sequence[i + 1]) { i--; }

`n`

represents the length of the sequence.- We start from the second-to-last element (
`n - 2`

) and move towards the beginning of the sequence. - We continue moving left as long as the current element is greater than or equal to the next element (non-increasing order).

At the end of this step, the variable `i`

will point to the element that needs to be swapped to generate the next permutation.

The next step is to locate the first element that needs to be swapped. This element is crucial for ensuring that the new permutation is lexicographically larger than the current one.

In the code, this step is not explicitly shown, but it's achieved by the value of `i`

obtained in the previous step. `i`

points to the first element that needs to be swapped.

To maintain the order of the original sequence, we find the smallest element in the suffix that is larger than the element identified in step 2.

In the code, this step is implemented as follows:

int j = n - 1; while (sequence[j] <= sequence[i]) { j--; }

- We start from the last element (
`n - 1`

) and move towards the beginning of the sequence. - We continue moving left as long as the current element is less than or equal to the element identified in step 2.

At the end of this step, the variable `j`

will point to the smallest element in the suffix that can replace the element identified in step 2 to create a lexicographically larger permutation.

Once we've identified the elements to swap in steps 2 and 3, we proceed to swap them to ensure that the new permutation is lexicographically larger. The elements are swapped as follows:

std::swap(sequence[i], sequence[j]);

This line of code swaps the elements at positions `i`

and `j`

in the sequence.

The final step involves reversing the suffix found in step 1 to achieve the smallest lexicographically larger permutation.

In the code, this step is implemented as follows:

std::reverse(sequence.begin() + i + 1, sequence.end());

- We use the
`std::reverse`

function to reverse the portion of the sequence from`i + 1`

to the end.

By following these steps, the code successfully generates the next lexicographically larger permutation, and the algorithm can be applied repeatedly to generate all possible permutations of the given sequence.

The next_permutation algorithm in C++ is used to generate the next lexicographically larger permutation of a sequence. It is a fundamental algorithm for tasks like generating permutations and combinations of elements.

To implement the next_permutation algorithm without the C++ STL, you can follow a step-by-step process. This includes finding the longest suffix with non-increasing order, identifying the first element to swap, locating the smallest element in the suffix, swapping the elements, and reversing the suffix. This approach allows you to generate the next lexicographically larger permutation.

It may be necessary to implement the next_permutation algorithm from scratch when you need to customize or modify the behavior of the algorithm for specific use cases. Additionally, if you are working in an environment where the C++ STL is not available or suitable, implementing it from scratch provides flexibility and control over the process.

Firebase & Angular.

Looking to learn how to create the production-ready apps

from scratch? Well, you are at the right place.

₹1299 or $15.56

## Learn to create the Dating App using No-Code Tool FlutterFlow

Level: **Advanced**

Mock Tests.

Test your C Programming skills with this comprehensive mock test on C Programming.

Take TestSolve most asked Interview Questions on Flutter and Test your foundational skills in flutter.

Take TestSolve most asked GATE Questions in Operating Systems and test your Gate Score.

Take TestThis is a mock test designed to help you assess your knowledge and skills in HTML and CSS.

Take TestSolve most asked GATE Questions in Data Structures and Algorithms and test your Gate Score.

Take TestMobile App