华体会真人平台

欢迎光临华体会真人平台
返回列表
您当前的位置:华体会真人平台 > 技术优势 > 基础知识 >
蓝桥杯省赛基础知识点 全排列函数和自写排列
发表于:2022-04-18 02:40 分享至:

  排列是计算机编程常用的基本技术,每一场算法竞赛都有题目用到排列。需要掌握两种实现排列的方法(C/C++组):

  (1)STL的next_permutation函数。需要输出所有的全排列时,直接用这个函数。

  (2)自写排列函数。如果只需要输出排列的一部分,此时用next_permutation函数无法做到,需要自己写代码。

  返回值:如果没有下一个排列组合,返回false,否则返回true。每执行next_permutation一次,会把新的排列放到原来的空间里。

  (2)next_permutation从当前的全排列开始,逐个输出更大的全排列,而不是输出所有的全排列。例如,初始序列是{b,c,a},它不是字典序最小的,此时只能输出3个。

  (3)如果要得到所有的全排列,需要从最小的全排列开始。如果初始的全排列不是最小的,先用sort排序,得到最小排列后,然后再执行next_permutation。例如:

  (4)如果序列中有重复元素,next_permutation生成的排列会去重。例如“aab”,代码输出3个排列{aab, aba, baa},不是6个排列。

  next_permutation虽然很方便,但是它不能打印n个数中取m个数的部分排列,在某些场合下需要在排列过程中做处理,此时必须自己写排列函数。

  下面自写一个全排列函数,它能实现部分排列。用递归写全排列函数,用b[]记录一个新的全排列,第一次进入bfs时,b[0]在n个数中选一个,第二次进入bfs时,b[1]在剩下的n-1个数中选一个,…,等等。用vis[]记录某个数是否已经被选过,选用过的数不能在后面继续选。

  代码能从小到大打印全排列,前提是a[]中的数字是从小到大的,先对a[]排序即可。

  如果需要打印n个数中任意m个数的排列,例如在4个数中取任意3个数的排列,把21行改为n = 4,然后在dfs中修改第7行,得下面的代码:

  下面给出一个需要自写全排列,不能用next_permutation的例子。

  题目是一个13!的全排列问题,如果用next_permutation,容易写出下面的代码:

  可惜,上述代码严重超时,因为13! = 6,227,020,800,运行代码,很久很久都无法结束。

  由于next_permutation每次都必须生成一个完整的排列,而不能在中间停止(只生成全排列的一部分,例如5个数的排列只输出排列的前3个),所以在这种场合下并不好用。

  分析题目可知,实际上并不用生成一个完整排列。例如一个排列的前3个数,如果不满足“□ + □ = □”,那么后面的9个数不管怎么排列都不对。这种提前终止搜索的技术叫“剪枝”,剪枝是搜索中常见的优化技术。下面的代码,在自写全排列的基础上加上了剪枝。

  本书是算法竞赛的入门和进阶教材,包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来,讲解清晰、透彻,帮助初学者建立自信心,快速从实际问题入手,模仿经典代码解决问题,进入中级学习阶段。

  全书分为12章,覆盖了目前算法竞赛中的主要内容,包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、高级数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。

  本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训,中学NOI信息学竞赛培训,以及需要学习算法、提高计算思维的计算机工作者。