std::
next_permutation
函数模板 <algorithm>| default (1) | template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last); |
| custom (2) | template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp); |
变换范围到下一个排列
将范围内的元素 [first,last)重新排列为下一个字典序上更大的排列。
排列就是元素可能采取的排列方式N!的一种(其中N是范围内的元素数量)。
不同的排列可以根据它们按字典顺序相互比较的方式进行排序;
第一个可能的排列(在字典上比所有其他排列都小的排列) 是所有元素都按升序排序的排列;最大的排列所有元素都按降序排序。
对于第一个版本，可以使用 operator<进行单个元素的比较，对于第二个版本，使用comp进行比较。
如果函数可以确定下一个更高的排列，它将重新排列元素，并返回true。 如果不能(因为它已经处于最大的可能排列)， 它将根据第一个排列(按升序排序)重新排列元素，并返回false。
☲ 参数
- first, last
-
指向序列初始和最终位置的双向迭代器。使用的范围是[first,last)，
它包含first和last之间的所有元素，包括first所指的元素，但不包括last所指的元素。
双向迭代器(BidirectionalIterator)应该指向一个正确定义了swap的类型。 - comp
-
二元函数,接受两个由BidirectionalIterator指向的类型的实参，
并返回一个可转换为bool类型的值。返回的值表明在它定义的特定严格弱排序中，
第一个参数是否被认为在第二个参数之前
函数不能修改它的任何参数。
它可以是一个函数指针，也可以是一个函数对象。
☉ 返回值
如果函数可以按照字典顺序的更大排列方式重新排列对象，则为true。
否则，函数返回false，表示排列不大于前一个，而可能是最小的(按升序排序)。
☣ 示例
// 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
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
✥ 复杂度
first and last之间距离的一半(根据实际交换)线性。
⇄ 数据竞争
范围[first,last)中的对象被修改。
☂ 异常安全性
如果元素比较或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| prev_permutation | 将范围转换为以前的排列(函数模板) |
| lexicographical_compare | 字典序小于比较(函数模板) |