Namespaces
Variants

    std::prev_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 prev_permutation( BidirIt first, BidirIt last );
    		(1) (C++20 起 constexpr) 
    template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp );
    		(2) (C++20 起 constexpr)

    变换范围 [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 必须满足 ValueSwappable 与 LegacyBidirectionalIterator 的要求。

    返回值

    若新排列在字典序中位于旧排列之前，则为 true 。若已到达首个排列且范围被重置为末位排列，则为 false 。

    异常

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

    复杂度

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

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

    可能的实现 

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

    注释

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

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

    示例

    以下代码按逆序输出字符串 "cab" 的全部六种排列。

    运行此代码 
    #include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "cab";
    do
    {
        std::cout << s << ' ';
    }
    while (std::prev_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

    输出： 

    cab bca bac acb abc cba

    参见

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