【STL】next_permutation 算法原理

参考:

基本思路

【STL】 next_permutation 函数就是返回当前序列的下一个字典序,已经为最大字典序则返回 False,否则为返回 True

基本思想如下:

  1. 从尾端开始依次比较两个相邻元素直到存在 ai,ai+1 满足 ai<ai+1,如果未找到返回 False
  2. 从尾端开始向前检验,找出第一个大于 ai 的元素 aj,交换 ai,aj
  3. ai 之后(不包括 ai)的序列做反序处理

可能的代码实现:

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

while (true) {
BidirIt i1, i2;

i1 = i;
if (*--i < *i1) {
i2 = last;
while (!(*i < *--i2))
;
std::iter_swap(i, i2);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}

简单证明

上面给出了思路,这里做一个简单证明

对一个序列 a0,a1,,ai,ai+1,,an1,必定存在 i,使得 aiai+1,为正序,ai+1an1 为逆序(这里正序指的是从小到大的顺序,逆序为从大到小),这里对应了上面的步骤 1

现在需要求此序列的下一个字典序,容易得到,ai+1an1 已经为逆序(也为递减数列),不存在更大的字典序,但 aian1,并不是逆序,即存在更大的字典序

显然以 ai 作为 aian1 的首元素已经达到最大,所以需要在 ai+1an1 中找到一个元素替换 ai,显然此元素为大于 ai 的最小元素,因为数列 ai+1an1 为递减数列,所以只需要从末端开始向前寻找第一个大于 ai 的元素即可,记此元素为 aj,即步骤 2

因为 aj>ai,所以 aj 作为首元素的最小排列为 ai+1an1 的顺序表示即可。交换后的序列仍然为逆序的,所以只需要反序处理即可,对应步骤 3