C++ Primer笔记——排列算法(next_permutation、prev_permutation、is_permutation)

目录

概述

①next_permutation

②prev_permutation

③is_permutation

概述

页数：P778 （A.2.7 排列算法） 

头文件：<algorithm>

函数名：next_permutation & prev_permutation & is_permutation

C++为我们提供了专门用于排列的算法。这些算法可以自动将内容按照字典序进行排列。

举个例子：现在有字符a、b、c，我们想要知道这三个字符有多少种组合方式，那么就可以用到排列算法。

①next_permutation

bool next_permutation(iterator first, iterator last);

bool next_permutation(iterator first, iterator last, compare comp);

前两个参数分别是待排列的数列头尾迭代器。第三个参数为自定义排列方式，默认是字典序。

每次排列都会改变数列的组合并返回true，既需要向前处理数列也需要向后处理，因此应该使用双向迭代器。

当排列到最后一种形式后（字典序最大的序列），会将数列排列成最小形式，同时返回false。

有两点非常值得注意：

1.排列的方式是数列从左往右按照字典序从小到大，以abc为例：排列为abc、acb、bac、bca、cab、cba。

这是因为abc的第一个元素（最左边）小于任何其他排列的首元素，且第二个元素也小于任何其他元素，以此类推。

2.next_permutation并不是把所有序列排出来，而是根据数列起始情况，向后排列。比如输入的序列是bac，那么排列出来只能是bac、bca、cab、cba。

示例代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<int> arr = { 1, 2, 3 };
	do
	{
		for (auto n : arr) cout << n << " ";
		cout << endl;
	} 
	while (next_permutation(arr.begin(), arr.end()));
	return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<int> arr = { 2, 3, 1 };
	do
	{
		for (auto n : arr) cout << n << " ";
		cout << endl;
	} 
	while (next_permutation(arr.begin(), arr.end()));
	return 0;
}

②prev_permutation

使用方式与next_permutation类似，只是该函数反向排列，即从起始序列开始向前排列。同样以abc为例，假如输入的序列是bac，那么prev_permutation输出的就是bac、acb、abc。

图示如下：

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<int> arr = { 3, 2, 1};
	do
	{
		for (auto n : arr) cout << n << " ";
		cout << endl;
	} 
	while (prev_permutation(arr.begin(), arr.end()));
	return 0;
}

③is_permutation

该函数用于确定某特定排序是否属于该序列。

bool next_permutation(iterator first1, iterator last1, iterator first2);

 函数前两个参数是指定排序的头尾迭代器，第三个参数是某序列的起始迭代器。

如果序列中存在这种排序，返回true；不存在就返回false。

当然，这里有两点需要注意的：

1.指定排序的长度需要小于等于序列长度。

2.第三个参数不一定非要是头迭代器。举例说明：假如指定排序为bac，序列为f a b c，那么第三个参数可以是beign() + 1，即从a开始排列，只排字母a b c。当然排多少个字母取决于指定排序的长度，这里是3。这也就是为什么指定排序的长度可以小于序列的长度。

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using namespace std;
int main()
{
	vector<int> arr = { 3, 2, 1 };
	vector<int> tmp = { 1, 2, 3 };
	if (is_permutation(arr.begin(), arr.end(), tmp.begin()))
	{
		cout << "right" << endl;
	}
	else cout << "false" << endl;
	return 0;
}

 特殊情况：

...
vector<int> arr = { 3, 2, 1 };
vector<int> tmp = { 4, 1, 2, 3 };
//没有从头迭代器开始排序， 待排序的序列元素为 1 2 3 
if (is_permutation(arr.begin(), arr.end(), tmp.begin() + 1))
    ...

...
vector<int> arr = { 3, 2, 1 };
vector<int> tmp = { 1, 2, 3, 4 };
//没有从头迭代器开始排序, 待排序的序列元素为 2 3 4
if (is_permutation(arr.begin(), arr.end(), tmp.begin() + 1))
    ...

如有错误，敬请斧正