本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie

next_permutation

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



描写叙述： 取得 [first, last) 所标示之序列的下一个排列组合。假设没有，返回 false，有，返回true

思路：

从后往前

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

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

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

源代码：

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) { //满足 *i < *ii

      BidirectionalIterator j = last;

      while (!(*i < *--j)); // 找到满足 *i < *j 的 *j

      iter_swap(i, j);

      reverse(ii, last); //将 ii右端的全部元素颠倒

      return true;

    }

    if (i == first) {

      reverse(first, last);//已经是最后一个排列了，逆向重排回到第一个排列

      return false;

    }

  }

}

演示样例：

int main()

{

	int a[] = {0,1,2,3,4};

	int n = sizeof(a)/sizeof(int);

	do{

		copy(a, a + n, ostream_iterator<int>(cout, " "));

		cout << endl;

	}while(next_permutation(a, a + n));

}