STL next_permutation 简单剖析

今天想学学全排列的非递归实现，但是搜索了半天，都是转载的同一篇文章，这篇文章的规律我还是没看懂。

想到c++的STL里有一个next_permutation()可以实现产生比当前序列大一点的下一个序列。

通过这种方法，也可以实现全排列的非递归实现。

 

STL源码下载：http://www.sgi.com/tech/stl/download.html

 

next_permutation()的原函数位于：stl_alog.h里面

内容如下：

// next_permutation and prev_permutation, with and without an explicitly 
// supplied comparison function.

template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
                 _LessThanComparable);
  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (*__i < *__ii) {
      _BidirectionalIter __j = __last;
      while (!(*__i < *--__j))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }
    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
}

 

基本思想如下：

从最后每相邻的两个进行比较，如果有前面一个比后面的小（i为较小位置，ii,为较大位置），那么此时一定存在一个排列比当前的大，然后是怎么产生这下一个排列。应该找这个较小的数的后面从最后开始比它大的第一个数，将它换到当前较小的位置上，然后将较大数ii到最后进行逆序。这样就产生了下一个排列。原理类似于，找到下一个较大的作为开始位的数，然后将后面的数字从最小开始即升序，例如原来为4653转换后为：5346

next_permutation()
{
        if  no element || only one element
               return false;

        i = last_element_ptr
        while(true)
        {
                 ii = i;    // the element before i
                 --i;
                 if  *i < *ii   // then there must be a sequence to change
                 {
                        j =  last_element_ptr
                        while( !(*i<*--j)   //find the first element from tail to head
                        {}                      //which is bigger than *i
                        swap(i, j)            // swap the  elements which i and j point to.
                         reverse(ii, last_element_ptr)  // reverse the array
                        return true;
                }
                if i == first_element_ptr   // if we to the head of the array, so no permutation
                {
                        reverse(first_element_ptr, last_element_ptr)
                        return false
                 }
         }


}

 

      从stl的next_permutation源码中我们看到，对于一个已经是最大权值的序列（即没有下一个比当前值大的排列），虽然返回值是false，但是它仍就将序列进行了逆序，例如对4321使用next_permutation后，序列变为1234.

看来读读久经考验的源代码是大有好处的。

 

      由此，我们就可以实现非递归的全排列了。呵呵 ，不用多说了吧。