std::next_permutation

`<algorithm>`
	(1)
`template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );`			(C++20)
`template< class BidirIt > constexpr bool next_permutation( BidirIt first, BidirIt last );`			(C++20)
		(2)
`template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );`				(C++20)
`template< class BidirIt, class Compare > constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );`				(C++20)

[first, last) operator< comp true (std::sort(first, last) ) false

first, last	-
comp	-	12 `true` (Compare ) `bool cmp(const Type1 &a, const Type2 &b);` `const &` `Type1` `Type2` ( const ) ( `Type1 &` `Type1` `Type1` (C++11)) `Type1` `Type2` `BidirIt`

- `BidirIt` ValueSwappable LegacyBidirectionalIterator

true false

swap

$N/2$ swap N = std::distance(first, last) 3 1.5 swap

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;

    while (true) {
        BidirIt 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;
        }
    }
}

"aba" 3

Run this code

#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()));
}

:

aab
aba
baa

is_permutation (C++11)	() [edit]
prev_permutation	() [edit]

cppreference.com

std::next_permutation