std:: prev_permutation

将范围 [ first , last ) 转换为前一个 排列 。若存在这样的排列则返回 true ，否则将范围转换为最后一个排列（如同通过 std::sort 后接 std::reverse 实现）并返回 false 。

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

参数

返回值

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

异常

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

复杂度

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

可能的实现

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

示例

#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

参见