STL next_permutation与prev_permutation函数

刷剑指offer遇到元素排列问题 No27 字符串的排列

函数使用

题目描述：

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

解题思路：

看到题解中一个很奇妙的函数next_permutation 和 prev_permutation

vector< string > Permutation(string str) {
    if (str.size() == 0)
        return vector< string >();
    vector< string > res;
    sort(str.begin(), str.end());
    do {
        res.push_back(str);
    } while (next_permutation(str.begin(), str.end()));
    return res;
}

使用手册：

std::next_permutation它用于将[first, last]范围内的元素重新排列到下一个字典上更大的排列。

即：abc下一个acb

std::prev_permutation它用于将[first, last]范围内的元素重新排列到上一个字典上更大的排列。

即：acb上一个abc

注意：next_permutation和prev_permutation必须用在已排好序的递增序列。

在《STL源码解析》中找到了这个函数，在此也简单叙述一下原理：

实现原理

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。前者是求出下一个排列组合，而后者是求出上一个排列组合。

所谓“下一个”和“上一个”，书中举了一个简单的例子：对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。
函数实现原理如下：
在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。
prev_permutation实现类似，就是反向查找。

总结

用next_permutation和prev_permutation求排列组合很方便，但是要记得包含头文件#include <algorithm>。
虽然最后一个排列没有下一个排列，用next_permutation会返回false，但是使用了这个方法后，序列会变成字典序列的第一个，如cba变成abc。prev_permutation同理。

参考文献：

1. https://www.iteye.com/blog/leonard1853-1450085
2. https://interviewguide.cn/notes/03-hunting_job/03-algorithm/02-sword-offer/27-剑指offer.html