STL中有关排列的函数还是很实用的

next_permutation

求下个排列

ii1 两个迭代器从尾部向前,满足 ++i == i1
找到第一组满足 *i < *i1 的位置
迭代器 i2 从后向前找到第一个满足 *i < *i2 的位置
交换ii2,然后 reverse(i1,last)

复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class Iterator>
bool next_permutation(Iterator first,Iterator last)
{
Iterator i = last;
if(first >= last || first == --i) return false;

for(;;)
{
Iterator i1 = i,i2;
if(*--i < *i1)
{
i2 = last;
while(!(*i < *--i2)) ;
swap(i,i2);
reverse(i1,last);
return true;
}
if(i == first)
{
reverse(first,last);
return false;
}
}
}

prev_permutation

求上个排列
next_permutation算法类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class Iterator>
bool prev_permutation(Iterator first,Iterator last)
{
Iterator i = last;
if(first >= last || first == --i) return false;

for(;;)
{
Iterator i1 = i,i2;
if(*i1 < *--i)
{
i2 = last;
while(!(*--i2 < *i)) ;
swap(i,i2);
reverse(i1,last);
return true;
}
if(i == first)
{
reverse(first,last);
return false;
}
}
}