std::next_permutation

From Cppreference

Transforms the range [first, last) into the next permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the first permutation (as if by std::sort(first, last)) and returns false.

[edit] Parameters

[edit] Return value

true if the new permutation is lexicographically greater than the old. false if the last permutation was reached and the range was reset to the first permutation.

[edit] Complexity

At most N/2 swaps, where N = std::distance(first, last).

[edit] Equivalent function

template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    if (first == last) return false;
    BidirectionalIterator i = last;
    if (first == --i) return false;
 
    while (1) {
        BidirectionalIterator i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

[edit] Example

The following code prints all three permutations of the string "aba"

#include <algorithm>
#include <string>
#include <iostream>
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Output:

aab
aba
baa

[edit] See also