C++ algorithm: std::next_permutation Function Template

C++ std::next_permutation

The algorithm std::next_permutation function rearranges the elements in a range into the next lexicographically greater permutation. If such a permutation is not possible (i.e., the elements are sorted in descending order), it rearranges the elements into the smallest (i.e., sorted in ascending order) permutation and returns false. This function is useful in generating permutations of a range.

---

Syntax of std::next_permutation

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

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

Parameters of std::next_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::next_permutation

Returns true if the function successfully rearranges the elements into the next permutation. Returns false if the elements are rearranged into the smallest permutation (i.e., sorted in ascending order).

---

Examples for std::next_permutation

Example 1: Basic Usage of std::next_permutation

This example demonstrates generating all permutations of a vector:

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

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

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

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::next_permutation function.
   • <vector>: Used for the std::vector container.
2. Initialize a vector:
   • A vector named nums is created and initialized with the elements {1, 2, 3}.
   • The elements in the vector are arranged in ascending order, which is required for std::next_permutation to generate all permutations.
3. Generate permutations:
   • The program uses a do-while loop to iterate through all permutations of the elements in nums.
   • The function std::next_permutation rearranges the elements in the next 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::next_permutation returns false, which happens when all permutations have been generated.

Output:

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

Example 2: Using a Custom Comparison Function for std::next_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 = {3, 2, 1};

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

    return 0;
}

Explanation:

1. Define a custom comparison function:
   • The function descending takes two integers as input.
   • It returns true if the first integer is greater than the second, ensuring that permutations are generated in descending order.
2. Generate permutations:
   • The program uses a do-while loop to iterate through all permutations of the elements in nums.
   • The function std::next_permutation is called with the range nums.begin() and nums.end(), and the custom comparison function descending as the third argument.
   • It rearranges the elements in the next descending lexicographical order and returns true if the rearrangement is possible. If no more permutations exist, it returns false.

Output:

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

---

Exception Handling in std::next_permutation

The std::next_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 = {1, 2, 3};

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

    return 0;
}

Explanation:

1. Define a custom comparison function:
   • The function faulty_compare compares two integers, a and b.
   • If either a or b equals 2, the function throws an exception std::runtime_error with the message "Comparison involving 2 is not allowed.".
   • Otherwise, it returns true if a is less than b.
2. Handle exceptions:
   • If faulty_compare throws an exception, the catch block captures it and prints the exception message using std::cerr.

Output:

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