C++ STL排列组合算法std::prev_permutation()函数入门

前面一节我们学习了排列组合算法——next_permutation()函数，读者是否还记得它的功能是什么吗？没错，它能让我们的序列按照字典序重新排列成下一个更大的组合。本节我们将学习它的对称函数——prev_permutation()函数。"prev"表示"前一个"，"permutation"表示"置换"，这里prev_permutation()函数的功能是将序列按照"字典顺序"重新排列成上一个更小的组合。

回顾一下，三个数1、2、3可以组合成6个三位数：123、132、213、231、312、321。如果我们从最大的排列321开始，使用prev_permutation()函数，就能依次得到312、231、213、132、123，正好是字典序的逆向遍历。这种从大到小的排列方式同样具有重要的应用价值。

prev_permutation()函数语法格式如下：

// 形式1：使用默认的 < 操作符进行比较
template< class BidirectionalIterator >
bool prev_permutation( BidirectionalIterator first,
                       BidirectionalIterator last );
// 形式2：使用自定义比较函数/函数对象  
template< class BidirectionalIterator, class Compare >
bool prev_permutation( BidirectionalIterator first,
                       BidirectionalIterator last,
                       Compare comp );

prev_permutation(first,last)函数的功能是对区间[first,last)中的元素重新排列为当前排列在字典序上的上一个更小的排列，该函数有返回值，数据类型为bool值，如果排序成功返回true，否则返回false。

下面我们通过代码对字符串"Dotcpp"进行一次逆向全排列（注意，想要逆向全排列需要先对序列进行降序排序），读者可以对比之前学习的内容，看看结果是否一致。

#include<iostream>
#include<vector>
#include<functional>
#include<cmath>
#include<algorithm>
using namespace std;
/*prev_permutation(first,last)函数*/ 
void test() {
    vector<char> v{'D','o','t','c','p','p'};
    vector<string> ret; // 存储所有排列的容器
    
    // 由于该函数会重新排列为当前排列在字典序上的上一个更小的排列，所以必须先降序排序
    sort(v.begin(), v.end(), greater<char>());//直接使用函数库对象 
    
    // 生成所有排列并存储（从大到小）
    do {
        string s(v.begin(), v.end()); // 迭代器初始化
        ret.push_back(s);
    } while (prev_permutation(v.begin(), v.end()));
    
    cout << "总共生成 " << ret.size() << " 个排列:" << endl;
    
    /*复习find()函数*/
    vector<string>::iterator pos = find(ret.begin(), ret.end(), "Dotcpp");
    if(pos != ret.end()) {
        cout << "找到【" << *pos << "编程】\n";
    } else {
        cout << "未找到【Dotcpp编程】\n";
    }
    
} 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

根据输出结果，我们同样生成了360个不同的组合；同时我们复习前面学习的find()函数，找到了"Dotcpp"这个字符串。与next_permutation()不同的是，这里输出的排列顺序是从大到小的字典序。

对比讨论一下这两个排列组合函数：next_permutation()，需要升序排序作为起点，生成下一个更大排列；prev_permutation()，需要降序排序作为起点，生成上一个更小排列。两个函数在遇到边界时（最大或最小排列）都会返回false，并将序列重置为另一端的排列。

总结：如果我们想要逆向遍历一个序列的全排列，可以使用prev_permutation(first,last)函数（前提是对该序列进行降序排序）；该函数同样返回bool类型，排序成功返回true，否则返回false。在蓝桥杯、ACM等算法竞赛上，prev_permutation()函数（需要从大到小枚举排列）常应用于暴力枚举、生成组合数、搜索剪枝和状态生成等。