std::prev_permutation

来自cppreference.com
< cpp‎ | algorithm

该页由英文版wiki使用Google Translate机器翻译而来。

该翻译可能存在错误或用词不当。鼠标停留在文本上可以看到原版本。你可以帮助我们修正错误或改进翻译。参见说明请点击这里.

点击这里参见该页的英文版本

 
C++
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
(C++11)
二分查找操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

重排
prev_permutation
数值操作
C 库
 
定义于头文件 <algorithm>
template< class BidirIt >
bool prev_permutation( BidirIt first, BidirIt last);
 (1)
template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp);
 (2)
变换的范围内[first, last)到先前从该组的所有字典顺序排列的排列相对于operator<或comp置换。返回true如果这样的排列存在，否则将到最后置换（如果由std::sort(first, last); std::reverse(first, last);），并返回false.
原文：
Transforms the range [first, last) into the previous permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the last permutation (as if by std::sort(first, last); std::reverse(first, last);) and returns false.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

目录

[编辑] 参数

first, last -
元素的范围内的重排
原文：
the range of elements to permute
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。
comp - 比较函数对象（即满足比较（Compare）要求的对象），若首个参数小于第二个，则返回 ​true 。

比较函数的签名应等价于如下者：

 bool cmp(const Type1 &a, const Type2 &b);

签名不需要拥有 const & ，但函数对象必须不修改传递给它的对象。
类型 Type1 与 Type2 必须使得 BidirIt 类型的对象能在解引用后隐式转换到这两个类型。 ​

类型要求
-
BidirIt 必须满足 ValueSwappable 和 BidirectionalIterator 的要求。

[编辑] 返回值

true如果之前的旧字典顺序排列。 false如果第一置换达到的范围内，被复位到最后置换.
原文：
true if the new permutation precedes the old in lexicographical order. false if the first permutation was reached and the range was reset to the last permutation.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

[编辑] 复杂度

在大多数(last-first)/2掉期.
原文：
At most (last-first)/2 swaps.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

[编辑] 可能的实现

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

[编辑] 示例

下面的代码打印出所有的字符串“ABC”以相反的顺序排列
原文：
The following code prints all six permutations of the string "abc" in reverse order
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

#include <algorithm>
#include <string>
#include <iostream>
#include <functional>
int main()
{
    std::string s="abc";
    std::sort(s.begin(), s.end(), std::greater<char>());
    do {
        std::cout << s << ' ';
    } while(std::prev_permutation(s.begin(), s.end()));
    std::cout << '\n';
}

输出： 

cba cab bca bac acb abc

[编辑] 另请参阅

(C++11)
 判断一个序列是否为另一个序列的排列组合
(函数模板) [编辑]
prev_permutation
 按字典顺序产生区间内元素下一个较小的排列组合
(函数模板) [编辑]
来自“http://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/prev_permutation&oldid=37871”