STL算法之permutation排列組合 · STL源碼剖析

### 前言 ? 由于在前文的《[STL算法剖析](http://blog.csdn.net/chenhanzhun/article/details/39698523)》中，源碼剖析非常多，不方便學習，也不方便以后復習，這里把這些算法進行歸類，對他們單獨的源碼剖析進行講解。本文講解的是STL算法中的permutation排列組合算法，根據輸入序列，排列出下一個排列組合或前一個排列組合。 ### permutation排列組合源碼剖析 ~~~ // next_permutation and prev_permutation, with and without an explicitly // supplied comparison function. //next_permutation獲取[first,last)區間所標示序列的下一個排列組合，若果沒有下一個排序組合，則返回false;否則返回true; /* 函數功能：Rearranges the elements in the range [first,last) into the next lexicographically greater permutation. 函數原型： default (1) ：版本一采用less-than操作符 template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); custom (2) ：版本二采用仿函數comp決定 template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); */ //版本一 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;//若為空，則返回false _BidirectionalIter __i = __first; ++__i; if (__i == __last)//區間只有一個元素 return false; //若區間元素個數不小于兩個 __i = __last;//i指向尾端 --__i;//不斷后移 for(;;) { //下面兩行是讓ii和i成為相鄰的元素 //其中i為第一個元素，ii為第二個元素 _BidirectionalIter __ii = __i;// --__i; //以下在相鄰元素判斷 if (*__i < *__ii) {//若前一個元素小于后一個元素， //則再從最尾端開始往前檢查，找出第一個大于*i的元素，令該元素為*j，將*i和*j交換 //再將ii之后的所有元素顛倒排序 _BidirectionalIter __j = __last;//令j指向最尾端 while (!(*__i < *--__j))//由尾端往前檢查，直到遇到比*i大的元素 {} iter_swap(__i, __j);//交換迭代器i和迭代器j所指的元素 reverse(__ii, __last);//將ii之后的元素全部逆向重排 return true; } if (__i == __first) {//進行到最前面 reverse(__first, __last);//整個區間全部逆向重排 return false; } } } //版本二 template <class _BidirectionalIter, class _Compare> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; ++__i; if (__i == __last) return false; __i = __last; --__i; for(;;) { _BidirectionalIter __ii = __i; --__i; if (__comp(*__i, *__ii)) { _BidirectionalIter __j = __last; while (!__comp(*__i, *--__j)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; } if (__i == __first) { reverse(__first, __last); return false; } } } //next_permutation函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort int main () { int myints[] = {1,2,3,4}; std::sort (myints,myints+4); std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] <<' ' << myints[3]<< '\n'; } while ( std::next_permutation(myints,myints+4) ); //std::next_permutation(myints,myints+4); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << ' ' << myints[3]<<'\n'; return 0; } Output: The 3! possible permutations with 3 elements: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 After loop: 1 2 3 4 */ //prev_permutation獲取[first,last)區間所標示序列的上一個排列組合，若果沒有上一個排序組合，則返回false;否則返回true; /* 函數功能：Rearranges the elements in the range [first,last) into the previous lexicographically-ordered permutation. 函數原型： default (1) ：版本一采用less-than操作符 template <class BidirectionalIterator> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last ); custom (2) ：版本二采用仿函數comp template <class BidirectionalIterator, class Compare> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); */ //版本一 template <class _BidirectionalIter> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __last) return false;//若區間為空，返回false _BidirectionalIter __i = __first; ++__i; if (__i == __last)//區間只有一個元素 return false;//返回false //若區間元素個數不小于兩個 __i = __last; --__i; for(;;) { //下面兩行是讓ii和i成為相鄰的元素 //其中i為第一個元素，ii為第二個元素 _BidirectionalIter __ii = __i; --__i; //以下在相鄰元素判斷 if (*__ii < *__i) {//若前一個元素大于后一個元素， //則再從最尾端開始往前檢查，找出第一個小于*i的元素，令該元素為*j，將*i和*j交換 //再將ii之后的所有元素顛倒排序 _BidirectionalIter __j = __last;//令j指向最尾端 while (!(*--__j < *__i))//由尾端往前檢查，直到遇到比*i小的元素 {} iter_swap(__i, __j); //交換迭代器i和迭代器j所指的元素 reverse(__ii, __last);//將ii之后的元素全部逆向重排 return true; } if (__i == __first) {//進行到最前面 reverse(__first, __last);//把區間所有元素逆向重排 return false; } } } //版本二 template <class _BidirectionalIter, class _Compare> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; ++__i; if (__i == __last) return false; __i = __last; --__i; for(;;) { _BidirectionalIter __ii = __i; --__i; if (__comp(*__ii, *__i)) { _BidirectionalIter __j = __last; while (!__comp(*--__j, *__i)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; } if (__i == __first) { reverse(__first, __last); return false; } } } //prev_permutation函數舉例 /* #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort, std::reverse int main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); std::reverse (myints,myints+3); std::cout << "The 3! possible permutations with 3 elements:\n"; do { std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( std::prev_permutation(myints,myints+3) ); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; return 0; } Output: The 3! possible permutations with 3 elements: 3 2 1 3 1 2 2 3 1 2 1 3 1 3 2 1 2 3 After loop: 3 2 1 */ ~~~ 參考資料：《STL源碼剖析》侯捷