C++ prev_ permutation & next_permutation functions [Tutorial]

In this article, we will learn about what permutations are, and the inbuilt functions for previous and next permutations in C++. Let us first start with the basics and understand what permutation is.

What are Permutations?

The mathematical notion of permutation describes the placement of things in a certain order. It is a way of selecting a set of objects and arranging them in a specific order, without repeating any of the objects.

A permutation of a set of n distinct objects is any ordering of these objects. The product of all positive numbers from 1 to n yields n! which is the total number of combinations that may be made out of n different things. For example, if n = 3, the possible permutations are:{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} and {3, 2, 1}.

Permutations can be represented as sequences, where the order of elements in the sequence determines the permutation.

For example, the permutation {1, 3, 2} can be represented as the sequence (2, 3, 1), where the first element represents the position of the object labeled "2" in the permutation, the second element represents the position of the object labeled "3", and the third element represents the position of the object labeled "1".

In programming, permutations are commonly used in algorithms and applications that involve generating or manipulating sequences, such as sorting algorithms, combinatorial optimization, and cryptography. The C++ Standard Library provides functions such as next_permutation() and prev_permutation() to generate permutations of a sequence.

These functions are based on lexicographic ordering, which means that the permutations are generated in alphabetical order, according to the ordering of the elements in the sequence.

C++ provides two functions prev_permutation() and next_permutation() that allow us to generate all possible permutations of a sequence in lexicographic order.

prev_permutation() in C++

The prev_permutation() function in C++ rearranges the elements of a sequence into the previous lexicographic permutation. It returns true if the sequence is rearranged to the previous permutation, and false otherwise if the sequence is already at its smallest permutation.

Here's an example of how to use prev_permutation() to generate all permutations of a vector of integers:

#include<iostream>
#include<algorithm> 
#include<vector> 

using namespace std;

int main() {
    vector<int> v = {1, 2, 3};

    do {
        for (int x : v) {
            cout << x << ' ';
        }
        cout << '\n';
    } while (prev_permutation(v.begin(), v.end()));

    return 0;
}

Output:

1 2 3

next_permutation() in C++

The C++ next_permutation() function works similarly to prev_permutation(), but generates the next lexicographic permutation instead of the previous one.

Here's an example of how to use next_permutation() to generate all permutations of a vector of integers:

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3};

    do {
        for (int x : v) {
            cout << x << ' ';
        }
        cout << '\n';
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

Output:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

Time & Space Complexity

The time complexity of the next_permutation() and prev_permutation() functions in C++ is O(n), where n is the size of the sequence. The algorithm used by both functions is based on lexicographic ordering.

The basic idea is to start with the largest index i such that the elements v[i] and v[i+1] are in decreasing order. Then, we find the largest index j greater than i such that v[j] > v[i]. We swap v[i] with v[j], and then reverse the order of the elements after index i, which gives the next permutation.

The prev_permutation() function works similarly but in reverse order. It starts with the largest index i such that the elements v[i] and v[i+1] are in increasing order, and finds the largest index j greater than i such that v[j] < v[i]. It then swaps v[i] with v[j], and reverses the order of the elements after index i.

Because both functions use a simple algorithm that involves only swapping and reversing operations, their time complexity is O(n).

However, the actual running time may depend on the complexity of the operations used to compare and swap the elements in the sequence, as well as the size of the sequence itself. In practice, these functions can be used efficiently for sequences with small to moderate sizes. For very large sequences, other algorithms may be more suitable.

The space complexity of the next_permutation() and prev_permutation() functions in C++ is O(1), which means that they require a constant amount of additional memory to generate permutations of a sequence.

Conclusion

In this article, we discussed how to implement the previous permutation and the next permutation in C++.