参考:
基本思路
【STL】 next_permutation
函数就是返回当前序列的下一个字典序,已经为最大字典序则返回
False,否则为返回 True
基本思想如下:
- 从尾端开始依次比较两个相邻元素直到存在 满足 ,如果未找到返回
False
- 从尾端开始向前检验,找出第一个大于 的元素 ,交换
- 将 之后(不包括 )的序列做反序处理
可能的代码实现:
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; } } }
|
简单证明
上面给出了思路,这里做一个简单证明
对一个序列 ,必定存在
,使得 ,为正序,
为逆序(这里正序指的是从小到大的顺序,逆序为从大到小),这里对应了上面的步骤
1
现在需要求此序列的下一个字典序,容易得到,
已经为逆序(也为递减数列),不存在更大的字典序,但 ,并不是逆序,即存在更大的字典序
显然以 作为
的首元素已经达到最大,所以需要在 中找到一个元素替换 ,显然此元素为大于 的最小元素,因为数列
为递减数列,所以只需要从末端开始向前寻找第一个大于 的元素即可,记此元素为 ,即步骤 2
因为 ,所以 作为首元素的最小排列为
的顺序表示即可。交换后的序列仍然为逆序的,所以只需要反序处理即可,对应步骤
3