C++ 标准库 permutation

2020-11-27 04:11

阅读：777

首先，permutation指的是对元素的重排，比如a , b , c 三个元素的所有的重排为 abc, acb, bac,bca,cab,cba 总共 3! = 6 中情况，但是如何声称这六种情况呢，C++标准库定义了函数 next_permutation，来生成一组元素的所有的全排列。

首先，了解该函数的声明以及实现：

函数声明为: [摘自 www.cplusplus.com]

std::next_permutation
default (1)
template 
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
custom (2)
template 
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
此两者在C++的标准库中被实现为模板的形式。

参数说明：

first last 其中的迭代器 first 和 last 用来表示元素的范围 [ first, last ) 不对称边界。

再来就是该迭代器的类型为双向迭代器，那么也就是说随机迭代器和双向迭代器可以作为该函数的参数传入。

Compare comp 是用来比较的函数，也就是说用来决定生成的重排的顺序函数，默认使用的是opeartor的比较函数，作为函数指针传入，或者是定义仿函数，传入函数对象，

返回值：

如果在该comp函数下，下一个重拍序列存在，则返回true，走则返回false，也就是说这一次的重拍序列已经是最后一个重排序列了。

比如，如果采用的是operator

副作用：

该函数会修改传入的元素顺序。

执行结果为：

可以看出，该函数会自动在当前的元素的顺序基础上，生成后续的排列。也就是说，如果要生成所有的permutation的话，那么需要先将元素排序。

default (1)	template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
custom (2)	template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);