### 前言
由于在前文的《[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源码剖析》侯捷
- 前言
- 空间配置器
- Traits编程技术
- STL源码剖析——迭代器
- 全局函数construct(),destroy(),uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()
- 序列容器之vector
- list容器的排序算法sort()
- 序列容器之list
- 序列容器之deque
- 容器配接器之stack
- 容器配接器之queue
- 容器配接器之priority_queue
- 最大堆heap
- 单向链表slist
- RB-Tree(红黑树)
- 关联容器之set
- stl_pair.h学习
- 关联容器之map
- 关联容器之multiset
- 关联容器之multimap
- 散列表hashtable
- stl_hash_fun.h学习
- 关联容器之hash_set
- 关联容器之hash_multiset
- 关联容器之hash_map
- 关联容器之hash_multimap
- 数值算法stl_numeric.h
- stl_relops.h学习
- 基本算法stl_algobase.h
- STL算法之set集合算法
- STL算法stl_algo.h
- STL算法之sort排序算法
- STL算法之find查找算法
- STL算法之merge合并算法
- STL算法之remove删除算法
- STL算法之permutation排列组合
- STL函数对象