STL 源代码分析 算法 stl_algo.h -- pre_permutation

本文senlie原版的，转载请保留此地址：http://blog.****.net/zhengsenlie

pre_permutation

----------------------------------------------------------------

描写叙述： 取得 [first, last) 所标示之序列的前一个排列组合。

假设没有，返回 false，有，返回true

思路：

从后往前

1.找两个相邻元素，令左端的元素为*i,右端的元素为*ii，且满足 *i > *ii

2.找出第一个小于 *i 的元素，令其为 *j。将*i,*j元素对调

3.将ii右端的全部元素颠倒

template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
  if (first == last) return false;
  BidirectionalIterator i = first;
  ++i;
  if (i == last) return false;
  i = last;
  --i;

  for(;;) {
    BidirectionalIterator ii = i;
    --i;
    if (*ii < *i) {  //满足 *ii < *i --> next_permutation 时的条件是 *i < *ii
      BidirectionalIterator j = last;
      while (!(*--j < *i)); // 找到满足 *j < *i 的 *j --> next_permutation 时的条件是 *i < *j
      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if (i == first) {
      reverse(first, last);
      return false;
    }
  }
}

演示样例：

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

  cout << "Initially:              ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  prev_permutation(A, A+N);
  cout << "After prev_permutation: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  next_permutation(A, A+N);
  cout << "After next_permutation: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

版权声明：本文博主原创文章，博客，未经同意不得转载。