**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.

10 OS Interview Questions you must know in 2024

10 Angular Interview Questions you must know in 2024

10 Javascript Interview Questions you must know in 2024

Top 10 DSA Interview Questions You should not miss

Top 10 Web Development Interview Questions

Introduction to Next.js

Altina Schinasi: Celebrating the Visionary Designer of Cat-Eye Frames | Google Doodle Tribute

Best Niche for Blogging in USA: A Comprehensive Guide

18 Must-Do Activities for Computer Science Students in College

13 Essential Things Solopreneurs need to know in 2024

25 Practical ways to earn money online

The Power of Gratitude - A Journey to Personal Growth

Top 5 Technology Trends That Are Shaping Our Future

5 Books You Need to Read Right Now

How to answer tell me about yourself?

What Angular feature transforms data before displaying it in the view?

Which widget is used in Flutter to create a button?

6 Mobile App Ideas That You Can Start in 2024

Flutter Widget Showdown: Exploring the Developers Favorite for Layouts!

Mobile App

For Engineers.

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 Test