next_permutation


类别：算法	组件类型：函数

原型

Next_permutation是一个重载名称；实际上有两个next_permutation函数。

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last);

template <class BidirectionalIterator, class StrictWeakOrdering>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
                      StrictWeakOrdering comp);

说明

Next_permutation转换元素范围[first，last)成为元素按字典序排列的下一个更大排列。存在有限数量的不同排列（最多为N! [1]，其中N是last - first），因此如果按lexicographical_compare对排列进行排序，则按字典序下一个排列可以明确定义。如果这样的排列存在，next_permutation转换为[first，last)该排列，并返回true。否则，它将转换为[first，last)按字典序最小的排列[2]，并返回false.

后置条件是元素的新排列按字典序比旧排列大（由lexicographical_compare确定），当且仅当返回值为true.

的两个版本next_permutation在如何定义一个元素是否小于另一个元素时存在差异。第一个版本使用operator<来比较对象，而第二个版本使用函数对象comp.

来比较对象

定义

在标准头文件 algorithm 中定义，在非标准后向兼容头文件 algo.h 中定义。

对类型的要求

对于采用两个参数的第一个版本，BidirectionalIterator
对于采用两个参数的第一个版本，是双向迭代器的模型。
对于采用两个参数的第一个版本，是可变的。
的值类型是可比较的 less than。对于采用两个参数的第一个版本，的值类型的排序关系是一个严格弱排序，如可比较的 less than 要求中定义的那样。

对于采用三个参数的第二个版本，

对于采用两个参数的第一个版本，BidirectionalIterator
对于采用两个参数的第一个版本，是双向迭代器的模型。
StrictWeakOrdering是严格弱排序的模型。
对于采用两个参数的第一个版本，的值类型可转换为StrictWeakOrdering的参数类型。

先决条件

[first，last)是一个有效的范围。

复杂性

线性。最多(last - first) / 2交换。

示例

此示例使用next_permutation来实现已知的最差确定性排序算法。大多数排序算法为O(N log(N))，即使冒泡排序也只有O(N^2)。此算法实际上为O(N!).

template <class BidirectionalIterator> 
void snail_sort(BidirectionalIterator first, BidirectionalIterator last)
{
  while (next_permutation(first, last)) {}
}

int main()
{
  int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
  const int N = sizeof(A) / sizeof(int);

  snail_sort(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, "\n"));
}

备注

[1]如果[first，last)中的所有元素彼此不同，那么完全有N!排列。但是，如果某些元素与彼此相同，排列的数量会减少。例如，只有三种（3!/2!）排列元素1 1 2.

[2] 请注意按词典顺序最小的排列定义上按非递减排列。

另请参见

prev_permutation, lexicographical_compare, 可比较的LessThan, 严格弱排序,排序