全排列算法的收集

全排列算法的收集1、introduction2、排列（permutation）定义：从一个n元（无重）集合s中取r个元素的有序安排。称为一个r排列，rn时，称为选排列，r=n时称为全排列。这种排列可想象将所排元素排为一条线也称线排列。圆形排列，也称环状排列，从n个物体取r个物体排成一个圆形，两个圆形排列，如果只差一个转动，则认为是相等的，n个物体中取r个物体的圆状排列数为!()!rnpnrrnr有重排列，从一个有重集合中取若干个元素的有序排列，称为有重排列。从有重集112{}kmnana取()irn个元素的排列数是rk，这里in可以是∞如果1kiinn,M中所有元素的排列（简称M的一个排列）数为12!!!!knnnn性质：（1）对于正整数n和rr≤n,有(1)(1)rnpnnnr（2）n个元素集合的r圆排列的个数由!()!rnpnrnrr给出，特别地，n个元素的全圆排列的个数是(1)!n算法1字典序法字典序：设,abp,0ab单项式11njjnfaxx，11nkkngbxx如果有1122,,,sskjkjkj，11sskj则称单项式g在单项式f之前，单项式中这种顺序关系称为字典序。字典序法给出了由一个排列12nppp生成下一个排列的算法。该算法归纳如下：（a）求满足关系式1jjpp的j的最大值，设为i，即1max{|}jjijpp(b)求满足关系式1jkpp的k的最大值，设为j，即1max{|}ikjkpp（c）1ip与jp互换得12().npppp（d）把1211()...iiinppppppp中1.iinppp部分的顺序逆转，得1211()...iniippppppp便是所求的下一个排列。例如：设1234pppp=1234，（a）1max{|}jjijpp=3(b)2max{|}kjkpp=3(c)2p与3p交换得2431(d)2431中的31顺序逆转得下一个排列2413证明：2序数法序数法基于一一对应的概念，因为!(1)!(11)(1)!(1)(1)!(1)!nnnnnnnn(1)!(2)(2)!(2)!nnnn故!(1)(1)!(2)(2)!(3)(3)!22!11!1nnnnnnn即!1(1)(1)!(2)(2)!(3)(3)!22!11!nnnnnnn定理：从0到!1n之间的任何整数m都可唯一的表示成1221(1)!(2)!2!1!nnmananaa其中0iai，1,2,,1in证明：因为满足条件0iai，11in的序列1,221(,)nnaaaa共有!n个，恰好与从0到!n-1的!n个整数一一对应。若使满足条件（2.1）的!n序列1,221(,)nnaaaa和具有n个元素的集合s的全部排列建立起一一对应关系，从而通过间接求解便可从序列1,221(,)nnaaaa得到一种生成排列的方法。为方便起见，不妨令n个元素分别为1，2，…，n对应规则如下：设序列{1,221(,)nnaaaa}对应某个排列12()npppp其中ia可以看作是排列()p中从数1i开始向右统计小于或等于i的数的个数，以排列4213为例，4后面比它小的数的个数（即3a）为3；3后面比它小的数的个数（即2a）为0；2后面比它小的数的个数（即1a）为1；排列中比1小的数是没有的。故有反过来，从也可获得一个排列