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.