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

前面一节我们学习了比较算法lexicographical_compare()函数，读者是否还记得它的功能是什么吗？没错，它能让我们的序列实现字典序比较行为。本节我们将学习排列组合算法——next_permutation()函数。“next”表示“下一个”，“permutation”表示“置换”，这里next_permutation()函数的功能将序列按照"字典顺序"重新排列成下一个不同的组合。

举个例子，比如我们有三个数1、2、3，我们可以组合成6个三位数：123、132、213、231、312、321。该排序方式理解起来也很简答，当只有一个数时，它只能组成一个数；当有两个数时，对比固定的一个数，新增的数有两个位置可以摆放，也就是能组成1*2个数；当只有3个数时，对比固定的两个数，新增的数有3个位置可以摆放，由于两个数本来就有两种情况，所以能组成3*2=6个数······不难发现这种排列方式具有递推性，并且我们称这种排列方式为“全排列”。比如3个数字组成三位数，我们用3!来表示（3！意思是1*2*3），以此类推。本节我们要学习的next_permutation()函数就能实现全排列。

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

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

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

下面我们通过代码对字符串"Dotcpp"进行一次全排列（注意，想要全排列需要先对序列进行升序排序），读者都知道它能排列出多少种不同的数吗？有读者可能会说是6!=720个数字，如果这样想的话是不对的，因为我们同时出现了两个’p‘，所以是6!/2!=320个字符串。原因也很简单，字母 'p' 出现了 两次，在计算排列总数时，完全相同的元素互换位置不会产生新的、不同的排列，所以我们要除以相同元素的阶乘。

#include<iostream>
#include<vector>
#include<functional>
#include<cmath>
#include<algorithm>
using namespace std;
/*next_permutation(first,last)函数*/ 
void test() {
     vector<char> v{'D','o','t','c','p','p'};
    vector<string> ret; // 存储所有排列的容器
    
    sort(v.begin(), v.end());//由于该函数会重新排列为当前排列在字典序上的下一个更大的排列，所以必须排序 
    
    // 生成所有排列并存储
    do {
        string s(v.begin(), v.end());//迭代器初始化 
        ret.push_back(s);
    } while (next_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(first,last)函数（前提是对该序列进行降序排序）；同时，读者还要知道该函数有返回值，类型为bool类型，排序成功返回true，否则返回false，在蓝桥杯、ACM等算法竞赛上该函数主要运用于暴力枚举、生成组合数、搜索剪枝和状态生成等。