蓝桥杯省赛基础知识点 | 全排列函数和自写排列
正值蓝桥杯省赛，这里发一篇很有用的基础知识点。
排列是计算机编程常用的基本技术，每一场算法竞赛都有题目用到排列。需要掌握两种实现排列的方法（C/C++组）：
（1）STL的next_permutation函数。需要输出所有的全排列时，直接用这个函数。
（2）自写排列函数。如果只需要输出排列的一部分，此时用next_permutation函数无法做到，需要自己写代码。
01
next_permutation
STL中求“ 下一个”全排列的函数是next_permutation。例如三个字符{a, b, c}组成的序列，next_permutation能按字典序返回6个组合：abc，acb，bac，bca，cab，cba。
函数next_permutation的定义有两种形式：
boolnext_permutation(BidirectionalIterator first, BidirectionalIterator last);
boolnext_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
返回值：如果没有下一个排列组合，返回false，否则返回true。每执行next_permutation一次，会把新的排列放到原来的空间里。
注意以下事项：
（1）next_permutation排列的范围是[first, last)，包括first，不包括last。
（2）next_permutation从当前的全排列开始，逐个输出更大的全排列，而不是输出所有的全排列。例如，初始序列是{b,c,a}，它不是字典序最小的，此时只能输出3个。
# include
usingnamespacestd;
intmain{
strings= "bca";
do{
cout<
} while(next_permutation(s.begin,s.end)); //end指向最后一个字符的下一个位置
return0;
}
代码只能输出3个全排列，而不是6个：
bca
cab
cba
（3）如果要得到 所有的全排列，需要从最小的全排列开始。如果初始的全排列不是最小的， 先用sort排序，得到最小排列后，然后再执行next_permutation。例如：
# include
usingnamespacestd;
intmain{
strings= "bca";
sort(s.begin,s.end); //字符串内部排序，得到最小的排列“abc”
do{
cout<
} while(next_permutation(s.begin,s.end));
return0;
}
此时能输出 所有的全排列，共6个：
abc
acb
bac
bca
cab
cba
（4）如果 序列中有重复元素，next_permutation生成的排列会去重。例如“aab”，代码输出3个排列{aab, aba, baa}，不是6个排列。
# include
usingnamespacestd;
intmain{
strings= "aab";
sort(s.begin,s.end); //字符串内部排序，得到最小的排列“abc”
do{
cout<
} while(next_permutation(s.begin,s.end));
return0;
}
输出3个排列：
aab
aba
baa
STL中还有一个 全排列函数prev_permutation，求“前一个”排列组合，与next_permutation相反，即“从大到小”。
next_permutation虽然很方便，但是 它不能打印n个数中取m个数的部分排列，在某些场合下需要在排列过程中做处理，此时必须自己写排列函数。
02
自写排列函数
下面自写一个全排列函数，它能实现部分排列。用递归写全排列函数，用b[]记录一个新的全排列，第一次进入bfs时，b[0]在n个数中选一个，第二次进入bfs时，b[1]在剩下的n-1个数中选一个，…，等等。用vis[]记录某个数是否已经被选过，选用过的数不能在后面继续选。
代码能从小到大打印全排列，前提是a[]中的数字是从小到大的，先对a[]排序即可。
# include
usingnamespacestd;
inta[ 20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
boolvis[ 20]; //记录第i个数是否用过
intb[ 20]; //生成的一个全排列
voiddfs( ints, intt) {
if(s == t) { //递归结束，产生一个全排列
for( inti = 0; i < t; ++i)
cout<< b[i] << " "; //输出一个排列
cout<< endl;
return;
}
for( inti= 0;i if(!vis[i]){ vis[i] = true; b[s] = a[i]; dfs(s+ 1,t); vis[i] = false; } } intmain{ intn = 3; dfs( 0,n); //前n个数的全排列 return0; } 输出： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 如果需要 打印n个数中任意m个数的排列，例如在4个数中取任意3个数的排列，把21行改为n = 4，然后在dfs中修改第7行，得下面的代码： # include usingnamespacestd; inta[ 20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; boolvis[ 20]; //记录第i个数是否用过 intb[ 20]; //生成的一个全排列 voiddfs( ints, intt) { if(s == 3) { //递归结束，取3个数产生一个排列 for( inti = 0; i < 3; ++i) //打印4个数中3个数的排列 cout<< b[i] << " "; cout<< endl; return; } for( inti= 0;i if(!vis[i]){ vis[i] = true; b[s] = a[i]; dfs(s+ 1,t); vis[i] = false; } } intmain{ intn = 4; dfs( 0,n); //前n个数的全排列 return0; } 输出： 1 2 3 1 2 4 1 3 2 1 3 4 1 4 2 1 4 3 2 1 3 2 1 4 2 3 1 2 3 4 2 4 1 2 4 3 3 1 2 3 1 4 3 2 1 3 2 4 3 4 1 3 4 2 4 1 2 4 1 3 4 2 1 4 2 3 4 3 1 4 3 2 03 例题 下面给出一个需要自写全排列，不能用next_permutation的例子。 寒假作业 （蓝桥杯2016年省赛C++A组第6题） 题目描述：加减乘除四种运算： □ + □ = □ □ - □ = □ □ × □ = □ □ ÷ □ = □ 每个方块代表1~13中的某一个数字，但不能重复。 问：一共有多少种方案？ 题目是一个13!的全排列问题，如果用next_permutation，容易写出下面的代码： # include usingnamespacestd; inta[ 20] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; intmain{ intans= 0; do{ if(a[ 0]+a[ 1]==a[ 2] && a[ 3]-a[ 4]==a[ 5] &&a[ 6]*a[ 7]==a[ 8] && a[ 11]*a[ 10]==a[ 9]) ans++; } while(next_permutation(a,a+ 13)); cout< } 可惜，上述代码严重超时，因为13! = 6,227,020,800，运行代码，很久很久都无法结束。 由于next_permutation每次都必须生成一个完整的排列，而不能在中间停止（只生成全排列的一部分，例如5个数的排列只输出排列的前3个），所以在这种场合下并不好用。 分析题目可知，实际上并不用生成一个完整排列。例如一个排列的前3个数，如果不满足“□ + □ = □”，那么后面的9个数不管怎么排列都不对。这种提前终止搜索的技术叫“剪枝”，剪枝是搜索中常见的优化技术。下面的代码，在自写全排列的基础上加上了剪枝。 # include usingnamespacestd; inta[ 20]={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; boolvis[ 20]; intb[ 20]; intans= 0; voiddfs( ints, intt) { if(s== 12) { if(b[ 9]*b[ 10] == b[ 11]) ans++; return; } if(s== 3&& b[ 0]+b[ 1]!=b[ 2]) return; //剪枝 if(s== 6&& b[ 3]-b[ 4]!=b[ 5]) return; //剪枝 if(s== 9&& b[ 6]*b[ 7]!=b[ 8]) return; //剪枝 for( inti= 0;i if(!vis[i]){ vis[i]= true; b[s]=a[i]; //本题不用a[]，改成b[s]=i+1也行 dfs(s+ 1,t); vis[i]= false; } } intmain{ intn= 13; dfs( 0,n); //前n个数的全排列 cout< return0; } 运行代码，很快就能输出答案： 64 04 参考书籍 《算法竞赛入门到进阶》 ISBN：978-7-302-52915-6 罗勇军 郭卫斌 编著 定价：59.8元 扫码优惠购书 ●内容简介● 本书是算法竞赛的入门和进阶教材，包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来，讲解清晰、透彻，帮助初学者建立自信心，快速从实际问题入手，模仿经典代码解决问题，进入中级学习阶段。 全书分为12章，覆盖了目前算法竞赛中的主要内容，包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、高级数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。 本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训，中学NOI信息学竞赛培训，以及需要学习算法、提高计算思维的计算机工作者。 05 精彩推荐 微信小程序游戏开发│猜数字小游戏（附源码+视频） Flink编程基础│Scala编程初级实践 Flink编程基础│FlinkCEP编程实践 Flink编程基础│DataStream API编程实践 Flink编程基础│DataSet API编程实践 数 据分析实战│客户价值分析 数据分析实战│价格预测挑战 数据分析实战│时间序列预测 数据分析实战│KaggleTitanic生存预测