function template
<algorithm>
std::next_permutation
| 預設 (1) | template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); |
|---|
| 自定義 (2) | template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); |
|---|
Transform range to next permutation
Rearranges the elements in the range [first,last) into the next lexicographically greater permutation.
A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare lexicographicaly to each other; The first such-sorted possible permutation (the one that would compare lexicographically smaller to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.
The comparisons of individual elements are performed using either operator< for the first version, or comp for the second.
If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false.
引數
- first, last
- Bidirectional iterators to the initial and final positions of the sequence. The range used is
[first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
BidirectionalIterator 應指向一個型別，該型別已正確定義了 swap。
- comp
- Binary function that accepts two arguments of the type pointed by BidirectionalIterator, and returns a value convertible to
bool. The value returned indicates whether the first argument is considered to go before the second in the specific strict weak ordering it defines.
該函式不得修改其任何引數。
This can either be a function pointer or a function object.
返回值
true if the function could rearrange the object as a lexicographicaly greater permutation.
Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).
示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// next_permutation example
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort
int main () {
int myints[] = {1,2,3};
std::sort (myints,myints+3);
std::cout << "The 3! possible permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while ( std::next_permutation(myints,myints+3) );
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
return 0;
}
|
輸出
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3
|
複雜度
Up to linear in half the distance between first and last (in terms of actual swaps).
資料競爭
範圍[first,last)內的物件將被修改。
異常
Throws if any element swap throws or if any operation on an iterator throws.
請注意，無效引數會導致未定義行為。