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

Exploring the Next_Permutation Algorithm without STL in C++

Article by: Manish Methani

Last Updated: September 8, 2021 at 10:04am IST
9 min 42 sec

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.

Table of Contents:

Introduction

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.

Understanding Permutations

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

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.

Step-by-Step Implementation

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.

Full Example Code

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

Output

 
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 

1. Find the Longest Suffix with Non-Increasing Order

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.

2. Identify the First Element to Swap

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.

3. Locate the Smallest Element in the Suffix

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.

4. Swap the Elements

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.

5. Reverse the Suffix

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.

FAQ

1. What is the purpose of the next_permutation algorithm in C++?

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.

2. How does the next_permutation algorithm work without using the C++ STL?

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.

3. When is it necessary to implement the next_permutation algorithm from scratch?

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.

Learn Flutter, FlutterFlow,
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

Explore Curriculum
₹1299 or $15.56

Flutter Mobile App Development Course

Explore Curriculum
₹1299 or $15.56

The Complete Angular Course

Explore Curriculum
₹1299 or $15.56

Dart Programming for Absolute Beginners

Coming Soon
FREE

Next.js course

Start Watching
FREE

Fundamentals of Computer Programming Languages

Start Watching
FREE

Learn HTML, CSS & Bootstrap

Start Watching

Latest Web Stories

1

Learn how to open WhatsApp using FlutterFlow | Step by Step Guide

Test your skills with these expert-led curated
Mock Tests.

C Programming Test

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

Take Test

Flutter Test

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

Take Test

GATE(CSE) Operating Systems

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

Take Test

HTML,CSS Test

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

Take Test

(GATE CSE) Data Structures & Algorithms Test

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

Take Test

Download the Codzify
Mobile App


Learn Anytime, Anywhere at your own pace. Scan the QR Code with your Mobile Camera to Download the Codzify Mobile App.

Codzify Mobile App Codzify Mobile App
Codzify Logo

Terms and Conditions    Cookie Policy   Refund Policy   Adsense Disclaimer