C++ algorithm: std::prev_permutation Function Template

C++ std::prev_permutation

The std::prev_permutation function in C++ rearranges the elements in a range into the previous lexicographically smaller permutation. If such a permutation is not possible (i.e., the elements are sorted in ascending order), it rearranges the elements into the largest (i.e., sorted in descending order) permutation and returns false. This function is useful for generating permutations of a range in reverse lexicographical order.

---

Syntax of std::prev_permutation

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

Parameters of std::prev_permutation

Parameter	Description
first, last	Bidirectional iterators defining the range of elements to permute. The range is [first, last).
comp (optional)	A binary comparison function that defines the criteria for comparing two elements. Defaults to <.

---

Return Value of std::prev_permutation

Returns true if the function successfully rearranges the elements into the previous permutation. Returns false if the elements are rearranged into the largest permutation (i.e., sorted in descending order).

---

Examples for std::prev_permutation

Example 1: Basic Usage of std::prev_permutation

This example demonstrates generating all permutations of a vector in reverse lexicographical order:

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

int main() {
    std::vector<int> nums = {3, 2, 1};

    do {
        for (int n : nums) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    } while (std::prev_permutation(nums.begin(), nums.end()));

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::prev_permutation function.
   • <vector>: Used for the std::vector container.
2. Initialize a vector:
   • A vector named nums is created and initialized with the elements {3, 2, 1}.
   • The elements are arranged in descending order, which is the required starting point for generating all permutations in reverse lexicographical order using std::prev_permutation.
3. Generate reverse permutations:
   • The program uses a do-while loop to iterate through all permutations of the elements in nums in reverse lexicographical order.
   • The function std::prev_permutation rearranges the elements in the previous lexicographical order and returns true if the rearrangement is possible. If no more permutations exist, it returns false.
4. Print each permutation:
   • Inside the loop, the program uses a for loop to iterate through the elements of the current permutation in nums and prints them separated by spaces.
   • After printing the elements of a permutation, a newline character is added to separate the outputs.
5. Continue until all permutations are generated:
   • The do-while loop continues until std::prev_permutation returns false, which happens when all permutations have been generated in reverse lexicographical order.
   • The program terminates after printing all reverse permutations of the vector nums.

Output:

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

Example 2: Using a Custom Comparison Function for std::prev_permutation

This example demonstrates generating permutations based on a custom comparison function:

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

bool descending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> nums = {1, 2, 3};

    do {
        for (int n : nums) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    } while (std::prev_permutation(nums.begin(), nums.end(), descending));

    return 0;
}

Explanation:

1. Define a custom comparison function:
   • The function descending compares two integers.
   • It returns true if the first integer is greater than the second, ensuring permutations are generated in descending lexicographical order.
2. Generate permutations:
   • The program uses a do-while loop to generate all permutations of the elements in nums in reverse lexicographical order based on the custom comparison.
   • The function std::prev_permutation is called with:
     • nums.begin(): Iterator pointing to the beginning of the vector.
     • nums.end(): Iterator pointing to the end of the vector.
     • descending: The custom comparison function.
   • The function rearranges the elements in the previous descending lexicographical order and returns true if the rearrangement is possible. If no more permutations exist, it returns false.

Output:

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

Exception Handling in std::prev_permutation

The std::prev_permutation function does not throw exceptions on its own. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates how exceptions in a custom comparison function are handled:

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

bool faulty_compare(int a, int b) {
    if (a == 2 || b == 2) {
        throw std::runtime_error("Comparison involving 2 is not allowed.");
    }
    return a < b;
}

int main() {
    std::vector<int> nums = {3, 2, 1};

    try {
        do {
            for (int n : nums) {
                std::cout << n << " ";
            }
            std::cout << std::endl;
        } while (std::prev_permutation(nums.begin(), nums.end(), faulty_compare));
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

3 2 1 
Exception caught: Comparison involving 2 is not allowed.