排列算法

MSTL排列算法的实现 更多...

函数
template<typename Iterator1, typename Iterator2, typename BinaryPred, enable_if_t< is_ranges_bid_iter_v< Iterator1 > &&is_ranges_bid_iter_v< Iterator2 >, int > = 0>
constexpr bool	is_permutation (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, BinaryPred pred)
	检查两个序列是否为排列关系
template<typename Iterator1, typename Iterator2>
constexpr bool	is_permutation (Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2)
	检查两个序列是否为排列关系
template<typename Iterator, typename Compare, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>
constexpr bool	next_permutation (Iterator first, Iterator last, Compare comp)
	生成下一个字典序排列
template<typename Iterator>
constexpr bool	next_permutation (Iterator first, Iterator last)
	生成下一个字典序排列
template<typename Iterator, typename Compare, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>
constexpr bool	prev_permutation (Iterator first, Iterator last, Compare comp)
	生成上一个字典序排列
template<typename Iterator>
constexpr bool	prev_permutation (Iterator first, Iterator last)
	生成上一个字典序排列

详细描述

MSTL排列算法的实现

函数说明

is_permutation() [1/2]

template<typename Iterator1, typename Iterator2>

bool is_permutation ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2 )

constexpr

检查两个序列是否为排列关系

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始
last2	第二个范围结束

返回

如果两个范围互为排列则返回true，否则返回false

在文件 permutation.hpp 第 87 行定义.

引用了 _MSTL , 以及 is_permutation().

is_permutation() [2/2]

template<typename Iterator1, typename Iterator2, typename BinaryPred, enable_if_t< is_ranges_bid_iter_v< Iterator1 > &&is_ranges_bid_iter_v< Iterator2 >, int > = 0>

bool is_permutation ( Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2, BinaryPred pred )

constexpr

检查两个序列是否为排列关系

模板参数

Iterator1	第一个迭代器类型
Iterator2	第二个迭代器类型
BinaryPred	二元谓词类型

参数

first1	第一个范围起始
last1	第一个范围结束
first2	第二个范围起始
last2	第二个范围结束
pred	相等性谓词

返回

如果两个范围互为排列则返回true，否则返回false

检查两个范围是否包含相同的元素（忽略顺序），但每个元素出现的次数必须相同。 算法首先检查长度是否相等，然后：

1. 如果两个范围完全相同（元素顺序和值都相同），立即返回true
2. 否则，对于第一个范围中的每个元素，统计在两个范围中出现的次数
3. 如果任何元素的计数不同，返回false

在文件 permutation.hpp 第 41 行定义.

引用了 _MSTL , 以及 distance().

被这些函数引用 is_permutation().

next_permutation() [1/2]

template<typename Iterator>

bool next_permutation ( Iterator first, Iterator last )

constexpr

生成下一个字典序排列

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

如果存在下一个排列则返回true，否则返回false

在文件 permutation.hpp 第 142 行定义.

引用了 _MSTL , 以及 next_permutation().

next_permutation() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>

bool next_permutation ( Iterator first, Iterator last, Compare comp )

constexpr

生成下一个字典序排列

模板参数

Iterator	迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

如果存在下一个排列则返回true，否则返回false（已经是最后一个排列）

将范围 [first, last) 变换为下一个字典序排列。 算法步骤（已知排列 P）：

1. 从右向左找到第一个满足 P[i] < P[i+1] 的位置 i
2. 从右向左找到第一个满足 P[i] < P[j] 的位置 j
3. 交换 P[i] 和 P[j]
4. 反转从 i+1 到结尾的部分

如果已经是最后一个排列（完全降序），则变换为第一个排列（完全升序）并返回false。

在文件 permutation.hpp 第 110 行定义.

引用了 _MSTL, iter_swap() , 以及 reverse().

被这些函数引用 next_permutation().

prev_permutation() [1/2]

template<typename Iterator>

bool prev_permutation ( Iterator first, Iterator last )

constexpr

生成上一个字典序排列

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

如果存在上一个排列则返回true，否则返回false

在文件 permutation.hpp 第 197 行定义.

引用了 _MSTL , 以及 prev_permutation().

prev_permutation() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>

bool prev_permutation ( Iterator first, Iterator last, Compare comp )

constexpr

生成上一个字典序排列

模板参数

Iterator	迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

如果存在上一个排列则返回true，否则返回false（已经是第一个排列）

将范围 [first, last) 变换为上一个字典序排列。 算法步骤（已知排列 P）：

1. 从右向左找到第一个满足 P[i] > P[i+1] 的位置 i
2. 从右向左找到第一个满足 P[j] < P[i] 的位置 j
3. 交换 P[i] 和 P[j]
4. 反转从 i+1 到结尾的部分

如果已经是第一个排列（完全升序），则变换为最后一个排列（完全降序）并返回false。

在文件 permutation.hpp 第 165 行定义.

引用了 _MSTL, iter_swap() , 以及 reverse().

被这些函数引用 prev_permutation().