两个函数类似，重点介绍next_permutation.
template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last );
template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
简介：得到下一个排列组合
默认是按字典序，比如abc->acb->bac->bca->cab->cba
算法描述：
1、从尾部开始往前寻找两个相邻的元素
第1个元素i，第2个元素j（从前往后数的），且i<j
2、再从尾往前找第一个大于i的元素k。将i、k对调
3、[j,last)范围的元素置逆（颠倒排列）
运行过程:
next: 01234
-> i=3,j=4
-> k=4,对调后01243
-> j指向最后一个元素，故结果为01243
next: 01243
-> i=2,j=4
-> k=3,对调后01342
-> j指向4，颠倒后为01324 即结果
...
next: 01432
-> i=1,j=4
-> k=2,对调后02431
-> j指向4，颠倒02134
按默认字典序的内部实现（带仿函数的类似)：
#include <algorithm>
#include <iostream>
template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
// 空区间
if(first == last)
return false;
BidirectionalIterator i = first;
++i;
// 只有一个元素
if(i == last)
return false;
// i指向尾部
i = last;
--i;
for (;;)
{
// i是j的上一个元素
BidirectionalIterator j = i;
--i;
if(*i < *j)
{
// 由尾部往前找到第一个比*i大的元素，并交换i,k
BidirectionalIterator k = last;
while(!(*i < *--k))
;
std::iter_swap(i, k);
// 将[j,last)的元素逆向重排
std::reverse(j, last);
return true;
}
// 到最前面了
if(i == first)
{
std::reverse(first, last);
return false;
}
}
}
int main()
{
int arr[] = {1, 2, 3};
do
{
std::cout<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<std::endl;
} while (next_permutation(arr, arr + 3));
prev_permutation()
// 到最前面的时候数组被reverse了
std::cout<<"last status: ";
std::cout<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<std::endl;
return 0;
}
prev_permutation与next_permutation不同之处就是
算法第一步：从尾部开始往前寻找两个相邻的元素
第1个元素i，第2个元素j（从前往后数的），且i>j(next_permutation条件是i<j)
亲：你明白了吗？