How to Use next_permutation in C++: Syntax and Examples

Use std::next_permutation from the <algorithm> header to rearrange elements into the next lexicographically greater permutation. It returns true if such a permutation exists, otherwise it returns false and resets to the smallest permutation.

Syntax

The std::next_permutation function rearranges elements in the range [first, last) to the next lexicographically greater permutation.

• first: Iterator to the beginning of the sequence.
• last: Iterator to one past the end of the sequence.
• Returns true if the function could rearrange to the next permutation, false if the sequence is already the highest permutation and resets to the lowest.

cpp

bool next_permutation(RandomIt first, RandomIt last);

Example

This example shows how to use std::next_permutation to print all permutations of a vector of integers in ascending lexicographical order.

cpp

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

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

    // Sort to start with the smallest permutation
    std::sort(nums.begin(), nums.end());

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

    return 0;
}

Output

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

Common Pitfalls

Common mistakes when using std::next_permutation include:

• Not sorting the sequence before the first call, which may skip permutations or produce unexpected order.
• Assuming it generates all permutations without resetting; it only generates the next permutation from the current order.
• Using it on non-random-access iterators, which is not supported.

cpp

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

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

    // This will start from {3,2,1} and generate permutations in descending order
    do {
        for (int num : nums) {
            std::cout << num << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(nums.begin(), nums.end()));

    return 0;
}

// Correct way: sort first
// std::sort(nums.begin(), nums.end());

Output

3 2 1 

Quick Reference

Tips for using std::next_permutation:

• Always sort your container before the first call to generate permutations in ascending order.
• Use a do-while loop to include the initial permutation.
• Works only with random-access iterators like vectors and arrays.
• Returns false when no next permutation exists, resetting to the lowest order.

Key Takeaways

Use std::next_permutation to get the next lexicographically greater permutation of a sequence.

Always sort the sequence before the first call to generate permutations in order.

The function returns false when the sequence is at its highest permutation and resets it.

Use a do-while loop to process all permutations including the initial one.

Works only with random-access iterators like vectors and arrays.