排列算法
排列的四种算法
排列算法
组合数学的主要问题：
存在性（满足一定条件的存在性）→数目（满足条件的数目）→算法设计→算法优化
排列生成算法：
（1）序数法（一一对应）
思路：先将排列和一种特殊的序列建立一一对应的关系，然后根据这种序列设计排列。 可以证明在0到（n-1）！这n个数中的任意整数m可以用下面的式子唯一的表示： m an 1(n 1) !an 2n( 2 )! a... 1!1
其中0 ai i，i 0,1,...n 1
满足上述条件的序列(an 1,an 2,....a2,a1)，共有n!个与0到m之间整数一一对应。 逆序数：指排列中逆序（排列中两个数的顺序与大小顺序相反）的总数。
序列(an 1,an 2,....a2,a1)与排列(p1p2...pn 1pn)一一对应，ai看成在排列中在数i 1后面比数i 1小的数的个数。
（2）字典序法
对给定的字符集中字符规定先后顺序，后面排列的数比前面排列的数大，即按字典排序的思想逐一产生排列。那么如何确定一个排列的下一个排列呢？
例：求排列（p）=p1p2...pn 1pn的下一个排列（q）。
找出最后一个正序：i max{j|pj 1 pj}
找出大于pi 1的最后一个数：j max{k|pi 1 pk}
互换pi 1和pj；
将pj后面的数反排，得到（q）。
（3）邻位互换法
由Johnson-Trotter提出，蕴含递归的思想。通过把n插入到n-1阶的全排列中的不同位置形成n阶全排列。在初始排列的每个数字上方加上←，若箭头所指的一侧的数小于当前数，那么当前数为活动状态。1一直为不活动状态，其他数在两种情况下为不活动状态：在排列的最左端且箭头向左；在排列的最右端且箭头向右。
实现n个数全排列的步骤：最开始排列为p1p2...pn，1、若排列中的活动数数目为0则停止，否则到2；2、找出当前活动数中最大的数m，将m与其上方箭头所指一侧的数进行交换；3、改变排列中所有比m大的数上方的箭头，回到1。
