Namespaces
Variants

    std::next_permutation

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围上的算法 (C++20)
    受约束算法，例如 ranges::copy、ranges::sort、...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分搜索操作
    (在已划分的范围上)
    集合操作（在已排序范围上）
    合并操作（在已排序范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <algorithm> 
    template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
    		(1) (constexpr 自 C++20) 
    template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );
    		(2) (constexpr 自 C++20)

    将范围 [first, last) 变换为下一个 排列。若存在这样的“下一个排列”则返回 true；否则将范围变换为字典序第一个排列（升序）并返回 false。

    1) 所有排列按字典序排序，相对于 operator<(至 C++20)std::less{}(C++20 起)。
    2) 所有排列按字典序排序，相对于 comp。

    若 *first 的类型不是 Swappable(至 C++11)BidirIt 不是 ValueSwappable(自 C++11)，则行为未定义。

    参数

    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 类型的对象在解引用后能隐式转换到这两个类型。

    类型要求
    -
    BidirIt 必须满足 LegacyBidirectionalIterator 的要求。

    返回值

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

    复杂度

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

    1,2) 最多进行
    N
    2
    次交换。

    异常

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

    可能的实现 

    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 时启用向量化。

    示例

    以下代码打印字符串 "aba" 的所有三种排列。

    运行此代码 
    #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

    另见

    (C++11)
    		 确定一个序列是否是另一个序列的排列
    (函数模板 & 算法函数对象)
    (C++20)
    		生成范围中元素的下一个较小字典序排列
    (函数模板 & 算法函数对象)
    (C++20)
    (C++20)
    		 生成范围中元素的下一个较大字典序排列
    (算法函数对象)