函数模板
<algorithm>

std::prev_permutation

默认 (1)
template <class BidirectionalIterator>  bool prev_permutation (BidirectionalIterator first,                         BidirectionalIterator last );
自定义 (2)
template <class BidirectionalIterator, class Compare>  bool prev_permutation (BidirectionalIterator first,                         BidirectionalIterator last, Compare comp);
将范围转换为前一个排列
将范围 [first,last) 中的元素重新排列成前一个字典序排列。

一个排列是元素可以采取的 N! 种可能排列中的每一种(其中 N 是范围中的元素数量)。不同的排列可以根据它们字典序的比较方式进行排序;第一个这种排序的可能排列(将与所有其他排列进行字典序比较更小的排列)是其所有元素按升序排序的排列,而最大的排列是其所有元素按降序排序的排列。

元素之间的比较是使用第一个版本的 operator< 或第二个版本的 comp 进行的。

如果函数能够确定前一个排列,它将元素重新排列成这样并返回 true。如果不可能(因为它已处于最低可能排列),它将元素重新排列成最后一个排列(按降序排序)并返回 false

参数

first, last
双向迭代器 指向序列的初始和最终位置。使用的范围是 [first,last),它包含 firstlast 之间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。
BidirectionalIterator 应指向一个类型,该类型已正确定义了 swap
comp
二元函数,接受由 BidirectionalIterator 指向的类型的两个参数,并返回一个可转换为 bool 的值。返回的值指示第一个参数在它定义的特定严格弱序中是否被认为排在第二个参数之前。
该函数不得修改其任何参数。
这可以是指针,也可以是函数对象。

返回值

如果函数能够将对象重排为字典序更小的排列,则返回 true
否则,函数返回 false,表示该排列不小于前一个,而是最大的可能排列(按降序排序)。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort, std::reverse

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);
  std::reverse (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::prev_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

输出
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
After loop: 3 2 1


复杂度

最多线性于 firstlast 之间距离的一半(以实际交换次数计)。

数据竞争

范围[first,last)内的对象将被修改。

异常

如果任何元素交换引发异常,或者任何迭代器操作引发异常,则抛出异常。
请注意,无效参数会导致未定义行为

另见