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

上一节我们学习了排列组合算法——prev_permutation()函数，读者是否还记得它的功能是什么吗？没错，该函数以降序排序作为起点，生成上一个更小排列。本节我们将学习判断是否为排列组合的算法——is_permutation()函数。"permutation"表示"置换"，这里is_permutation()函数的功能是判断两个序列是否互为彼此的排列组合，比如我们有两个序列：序列1{'D' , 'o' , 't' , 'c' ,'p' , 'p'}，序列2{'D' , 'o' , 't' , 'p' ,'c' , 'p'}，我们传入这两个序列的区间[起始迭代器，尾后迭代器）作为参数，因为这两个序列都有1个'Dotc'，两个'p'，所以我们得到true的返回值。

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

// 形式1：使用默认的 == 操作符进行比较
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2 );
// 形式2：使用自定义比较函数/函数对象
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2,
                     BinaryPredicate p );
// 形式3：指定第二个序列的完整范围（C++14起）
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );
// 形式4：指定第二个序列范围 + 自定义比较（C++14起）
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2,
                     BinaryPredicate p );

细心的读者可能发现，为什么第二个序列有时没有尾后迭代器，有时又有尾后迭代器呢？原因在于很久之前该函数默认第二个序列长于第一个序列，程序员们已经习惯这种参数规则了，但是由于后面出现数组越界等未定义行为，导致程序崩溃，所以后面要求补充第二个序列的尾后迭代器，时刻提醒开发者避免数组越界，这里也是强烈推荐读者使用完整的迭代器区间。

prev_permutation(first1,last1,first2,last2)表示对比两个序列[first1,last1)，[first2,last2)是否互为彼此的排列组合，简单来说就是比较两个序列在元素上是否相同且在数量上是否相等。下面我们通过代码来简单演示一下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
/*is_permutation(first1,last1,first2)函数*/ 
void test() {
    vector<char> v1{'D','o','t','c','p','p'};
    vector<char> v2{'D','o','t','p','c','p'};
     
    // 判断v1和v2是否互为排列组合
    if(is_permutation(v1.begin(), v1.end(), v2.begin())) 
    {
        string s1(v1.begin(),v1.end());
        string s2(v2.begin(),v2.end());
        cout <<"【"<< s1 << "】 和 【" << s2 << "】 互为排列组合\n";
    }
    else 
    {
        string s1(v1.begin(),v1.end());
        string s2(v2.begin(),v2.end());
        cout <<"【"<< s1 << "】 和 【" << s2 << "】 不互为排列组合\n";
    }
} 
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

因为序列1{'D' , 'o' , 't' , 'c' ,'p' , 'p'}和序列2{'D' , 'o' , 't' , 'p' ,'c' , 'p'}在元素上是否相同且在数量上是否相等，所以它两互为排列组合，输出符合预期！

当然，本节的学习并非止步于此，如果两个序列需要进行模糊比较，我们可以对prev_permutation(first1,last1,first2,last2)函数添加一个二元谓词。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

bool pred(const float&f1,const float&f2)
{
	return (abs(f1-f2)>=0&&abs(f1-f2)<=1);
}
/*is_permutation(first1,last1,first2)函数*/ 
void test() {
    vector<float> v1{1.1,2.2,3.3,4.4,5.5};
    cout << "v1存储的小数有：";
	for(auto it = v1.begin();it!=v1.end();++it) cout << *it << " ";
	cout << '\n';
    vector<float> v2{1.2,2.3,3.4,4.5,5.6};
    cout << "v2存储的小数有：";
	for(auto it = v2.begin();it!=v2.end();++it) cout << *it << " ";
	cout << '\n';
     
    // 判断v1和v2是否互为排列组合
    if(is_permutation(v1.begin(), v1.end(), v2.begin(),pred))
    {
        cout <<"在自定义比较下，v1==v2\n";
    }
    else 
    {
       cout <<"在自定义比较下，v1!=v2\n";
    }
} 

int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

通过自定义模糊比较，由于v1中的每个元素都能在v2中找到差值在[0,1]范围内的唯一对应元素，且反之亦然，所以is_permutation返回true。

其实，谓词部分我们可以用Lambda表达式来替换，该表达式又被称为匿名函数。那什么是Lambda表达式呢？Lambda 表达式是一种无需定义函数就能创建函数对象的方法。它可以在需要函数的地方直接定义和使用，特别适合用于回调函数、算法参数等场景。其语法格式如下：

[capture](parameters) -> return_type {
    function_body
}

/*各参数解释*/
/*[capture]：捕获列表，定义 Lambda 如何访问外部变量*/
/*(parameters)：参数列表，与普通函数参数类似*/
/*-> return_type：返回类型（可省略，编译器自动推导）*/
/*{function_body}：函数体，包含要执行的代码*/

比如上面这个模糊比较我们就可以使用Lambda表达式来简化普通函数。

if(is_permutation(v1.begin(), v1.end(), v2.begin(),[](const float&f1,const float&f2){
    return (abs(f1-f2)>=0&&abs(f1-f2)<=1);}))
    {
        cout <<"在自定义比较下，v1==v2\n";
    }
    else 
    {
       cout <<"在自定义比较下，v1!=v2\n";
    }

通过使用Lambda表达式来简化普通函数或仿函数，更便捷和直接。

总结：如果想要比较两个序列是否互为排列组合，我们就可以使用is_permutation()函数；如果想要进行自定义比较，我们就可以添加二元谓词参数，同时可以利用匿名函数来简化普通函数或仿函数；在蓝桥杯、ACM等算法竞赛上，is_permutation()函数常应用于数据验证、字符串匹配、组合数学问题和算法优化等场景，是解决排列相关问题的利器。