stl当中的permutation函数

当第一眼看见这个函数名字的时候，还以为是求卡特兰数，结果不是，是发现排列组合规律的一个函数。

已知：容器当中有一系列的元素

求：当容器当中的元素满足一定的比较关系时，当前容器内的元素对应的排列组合的下一个排列组合

例如：当前序列为{b, c, a}, 其共有三个元素，有3！个排列组合即：

a, b, c;

a, c, b;

b, a, c;

b, c, a;

c, a, b;

c, b, a;

那么当前序列的next_permutation为：{c, a, b}, prev_permutation为：{}b, a, c},

在这个过程当中简而言之：从最尾端开始向前寻找两个相邻元素，找到第一对满足后面的元素（b）比前面的元素（a）的值大；下一步在较小值(a)之后，从尾端开始寻找到第一个大于a的值（c），将c与a交换，之后再将b之后的元素颠倒排序，代码如下：

template <class BidirectionalIterator>
bool next_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 (*i < *ii) {
      BidirectionalIterator j = last;
      while (!(*i < *--j));
      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if (i == first) {
      reverse(first, last);
      return false;
    }
  }
}

prev_permutation的思路跟next_permutation的思路差不多，就是查找条件不一样，这里直接上代码了哈~

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) {
      BidirectionalIterator j = last;
      while (!(*--j < *i));
      iter_swap(i, j);
      reverse(ii, last);
      return true;
    }
    if (i == first) {
      reverse(first, last);
      return false;
    }
  }
}

Stl就先讲到这里吧~~