std::next_permutation() 算法

自 C++20 起

// (1)
template< class BidirIt >
constexpr bool next_permutation( BidirIt first, BidirIt last );

// (2)
template< class BidirIt, class Compare >
constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );

直到 C++20

// (1)
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );

// (2)
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

将范围 [first; last) 排列成下一个排列，其中所有排列的集合根据 operator< 或 comp 按字典顺序排列。

如果存在这样的“下一个排列”，则返回 true；否则，将范围转换为字典序的第一个排列（如同通过 std::sort(first, last, comp)）并返回 false。

参数

first last	要排列的元素范围。
comp	比较函数对象（即满足 Compare 要求的对象），如果第一个参数小于第二个参数，则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受所有（可能为 const）Type1 和 Type2 类型的值，无论值类别如何（因此不允许 Type1&，也不允许 Type1，除非对于 Type1，移动等同于复制 (自 C++11 起)） Type1 和 Type2 类型必须能够使 BidirIt 类型的对象隐式转换为它们两者。

类型要求

ForwardIt

ValueSwappable LegacyBidirectionalIterator

返回值

如果新排列在字典序上大于旧排列，则为 true。
如果达到了最后一个排列并且范围被重置为第一个排列，则为 false。

复杂度

给定 N 为 std::distance(first, last)

最多 N / 2 次交换。平均在整个排列序列中，典型实现每次调用大约使用 3 次比较和 1.5 次交换。

异常

迭代器操作或元素交换可能抛出的任何异常。

可能的实现

实现（例如 MSVC STL 可能会在迭代器类型满足 LegacyContiguousIterator 且交换其值类型不调用非平凡的特殊成员函数或 ADL 找到的 swap 时启用矢量化。

next_permutation (1)

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);

    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }

    std::reverse(left.base(), last);
    return left != r_last;
}

示例

Main.cpp

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s = "aba";

    do std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));

    std::cout << s << '\n';
}

输出

aba
baa
aab