std::next_permutation

来自cppreference.com

 
 
算法库
功能
Original:
Functions
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
修改序列操作
Original:
Non-modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
all_of
any_of
none_of
(C++11)
(C++11)
(C++11)
for_each
count
count_if
mismatch
equal
修改序列操作
Original:
Modifying sequence operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
分区操作
Original:
Partitioning operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
is_partitioned(C++11)
partition
partition_copy(C++11)
排序操作(排序的区间)
Original:
Sorting operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
is_sorted(C++11)
is_sorted_until(C++11)
sort
二进制搜索操作(排序的区间)
Original:
Binary search operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
设置操作(排序的区间)
Original:
Set operations (on sorted ranges)
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
堆的操作
Original:
Heap operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
最小/最大操作
Original:
Minimum/maximum operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
数字操作
Original:
Numeric operations
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
C库
Original:
C library
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
 
Defined in header <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.
Original:
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.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

目录

[编辑] 参数

first, last -
元素的范围内的重排
Original:
the range of elements to permute
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

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

The signature does not need to have const &, but the function must not modify the objects passed to it.
The types Type1 and Type2 must be such that an object of type BidirIt can be dereferenced and then implicitly converted to both of them. ​

Type requirements
-
BidirIt must meet the requirements of ValueSwappable and BidirectionalIterator.

[编辑] 返回值

true如果新的排列是大于旧字典。 false如果最后的排列,达到的范围复位到第一排列.
Original:
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.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[编辑] 复杂性

在最N/2掉期,N = std::distance(first, last).
Original:
At most N/2 swaps, where N = std::distance(first, last).
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[编辑] 可能的实现

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”字符串的所有排列
Original:
The following code prints all three permutations of the string "aba"
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

#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()));
}

Output:

aab
aba
baa

[编辑] 另请参阅

(C++11)
判断一个序列是否为另一个序列的排列组合
(函数模板) [edit]
按字典顺序产生区间内元素下一个较小的排列组合
(函数模板) [edit]