我们自然知道C++的STL提供了丰富的基本数据结构以及算法支持,但事实上在使用中,我们常常容易忽略它,因为学习STL本身也需要一定的时间成本。STL基于泛型编程(Generic Programming, GP),很多人看到这个术语就打了退堂鼓,之内诸如迭代器之流,也更是云里雾里,不知所云也不想探究之,所以明明很好的工具就在手边,但是却弃之不用,着实可惜。
认识这个函数纯属偶然,今天在POJ上做题,看到了一道题[1]的Discuss中提示使用这个函数会使大大简化题目的难度,那么这个函数究竟就以用来做什么呢?
从标题我们就可以知道,可以这个函数用来获取一组元素的全排列,根据其定义,当你输入一组元素后,函数会将这组元素进行排列,排列结果为这组元素按字典序的下一个排列。这里先解释两个名词:一个是字典序,一个是全排列。
所谓字典序,顾名思义,就是像字典上那样的规则对元素进行排列:
我这里从身旁随手的一本字典翻开一页,单词如下:

career
careerist
carefree
careful
careless

这个规律我们很容易看到,那就是从第一个字母开始比较,如果字母在字母表的位置不同,则靠前的字母排在前面,否则按此规则比较下一个字母。这就是字典序的排列方法。
那么什么是全排列呢?这是排列组合中的概念,给定一组元素,我们来给他们随意的交换位置,对于不同位置的情况的集合,我们几句称之为全排列。对于n个不同的元素,其全排列的数量为n!。我们来举个例子:
对于集合{1, 2, 3}中的元素而言,其全排列的数目为3! = 6
分别为

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

*由于集合是具有无序性的,所以我们这里考虑的是有序数组,用[]作为记号
上面列出的全排列满足之前所说的字典序。
那么next_permutation()函数的具体作用呢?假如输入的有序数组是[2, 1, 3],那么这个函数就会把这个数字重排为[2, 3, 1],这也就是所谓的按字典序全排列的下一个。
对于一个已经按从小到大排列好的整型数组A[N],我们可以用这样的方法输出其全排列,是不是很简单呢?

要使用这个函数,需要引用C++标准库算法头文件<algorithm>;,在这个文件中我们可以找到这个函数的代码(这个函数有两个重载,带有三个参数的重载要求填入一个比较参数,这里我们只需看两个参数的那个,默认比较为“小于”):

标准库的代码并不是很难理解,稍显晦涩只是其中包含了一些错误检测功能而已,其目的也是保障算法的健壮性。我稍微修改了下代码的缩进,因为原来的缩进风格,我自认为不是很舒服。
函数输入的两个参数为迭代器(或地址),也就是说可以使用解引用运算符(*),同时要求该数据类型可以使用小于号这个运算符,如果下一个不存在一个排列满足其字典序比现有有序数组大,那么就将这个数组排为最小字典序(转了一个圈),并返回false。对照注释我们可以看到,其实算法本身并不复杂,STL中的注释,已经说得很明白了,我在代码中加入自己的理解小小的翻译一下。
使用标准库,可以极大的简化我们的编程工作,甚至于在竞赛中,允许使用C++,通常就意味着可以使用C++标准库,因为二者是官方配套的,并不是MS什么的第三方库。
与这个函数对应的,还有一个prev_permutation,用于获取字典序的前一个排列,算法大同小异,有兴趣可以看看。
使用这个函数,可以在三四行之内解决POJ的两个问题,一个是刚才提到的[1],还一个也请看链接[2]

[1] POJ 1146 ID Codes
[2] POJ 1833 排列

说点什么

  Subscribe  
提醒