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，兩者都是用來計算排列組合的函數。前者是求出下一個排列組合，而後者是求出上一個排列組合。