std::next_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)

重排
next_permutation
数值操作
C 库
 
定义于头文件 <algorithm>
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
 (1)
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );
 (2)
变换的范围内[first, last)进入下一置换从该组的所有字典顺序排列的排列相对于operator<或comp。返回true如果这样的排列存在，否则将到第一个置换（如果由std::sort(first, last)），并返回false.
原文：
Transforms the range [first, last) into the next 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 first permutation (as if by std::sort(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 is lexicographically greater than the old. false if the last permutation was reached and the range was reset to the first permutation.
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里。

[编辑] 复杂度

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

[编辑] 可能的实现

template<class BidirIt>
bool next_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 (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

[编辑] 示例

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

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

输出： 

aab
aba
baa

[编辑] 另请参阅

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