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.

Simplified Coding for Beginners.








Download the Codzify
Mobile App


Mobile App Development, Web App Development, Programming Languages, Latest Tech News & lot more.

Codzify Mobile App

A self-paced learning Courses Created by an Engineer
For Engineers.

Premium

The Complete Angular Course

Instructor: Manish Methani

Explore Curriculum
Free

C Programming for Absolute Beginners

Instructor: Manish Methani

Start Watching
Premium

Flutter Mobile App Development Course

Instructor: Manish Methani

Explore Curriculum
Free

Learn HTML, CSS & Bootstrap

Instructor: Manish Methani

Start Watching

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
include_once 'codzify-footer.php'; ?>