C++ STL next_permutation的實現原理

next_permutation得到下一個排列，如對序列 a, b, c，每一個元素都比後面的小，它的下一個序列即為a, c, b

next_permutation的函數原型如下：
 

template<class BidirectionalIterator>
 bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
 );
 template<class BidirectionalIterator, class BinaryPredicate>
 bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
  );

函數實現原理如下：
 在當前序列中，從尾端向前尋找兩個相鄰元素，前一個記為*i，後一個記為*t，並且滿足*i < *t。然後再從尾端尋找另一個元素*j，如果滿足*i < *j，即將第i個元素與第j個元素對調，並將第t個元素之後（包括t）的所有元素顛倒排序，即求出下一個序列了。

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 t = i;
        --i;
        if(*i < *t) {
            BidirectionalIterator j = last;
            while(!(*i < *--j));
 
            iter_swap(i, j);
            reverse(t, last);
            return true;
        }
       
        if(i == first) {
            reverse(first, last);  //全逆向，即為最小字典序列，如cba變為abc
            return false;
        }
    }
 }

所以如果到最後一個排列next_permutation會返回false，但是使用了這個方法後，序列會變成字典序列的第一個，如cba變成abc。就可以繼續next了，可以參考next_permutation的用法，http://www.linuxidc.com/Linux/2013-04/82497.htm
 

在STL中，除了next_permutation外，還有一個函數prev_permutation，兩者都是用來計算排列組合的函數。前者是求出下一個排列組合，而後者是求出上一個排列組合。