std:: next_permutation

将区间 [ first , last ) 重新排列为下一个 排列 。若存在“下一个排列”则返回 true ；否则将区间变换为字典序首排列（如同通过 std::sort ），并返回 false 。

如果 * first 的类型不满足 Swappable 要求 (C++11 前) BidirIt 不满足 ValueSwappable 要求 (C++11 起) ，则行为未定义。

参数

返回值

若新排列按字典序大于原排列则为 true 。若已到达最终排列且范围已被重置为首个排列则为 false 。

复杂度

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

异常

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

可能的实现

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;
}

注释

在整个排列序列的平均情况下，典型实现每次调用大约使用3次比较和1.5次交换。

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

示例

#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

参见