std::next_permutation
来自cppreference.com
![]() |
This page has been machine-translated from the English version of the wiki using Google Translate.
The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here. |
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.
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. |
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.
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.
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.
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) |
判断一个序列是否为另一个序列的排列组合 (函数模板) |
按字典顺序产生区间内元素下一个较小的排列组合 (函数模板) |