std::prev_permutation() 算法

自 C++20 起

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

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

直到 C++20

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

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

将范围 [first; last) 排列成前一个排列，其中所有排列的集合相对于 operator< 或 comp 按字典序排序。

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

参数

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

类型要求

ForwardIt

ValueSwappable LegacyBidirectionalIterator

返回值

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

复杂度

最多 (last - first) / 2 次交换。

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

异常

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

可能的实现

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

prev_permutation (1)

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

示例

Main.cpp

#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