几种排列生成算法的数学原理解析
对于有限数列:
易知其共有 n! 个不同的排列。为了在枚举这些排列时不遗漏,需要定义一种遍历规则,这种遍历规则便称为计数法。
计数法可分为两类:树图法、逆序法。
中介数:
中介数记录了一个排列的全部信息,根据中介数可以确定的写出一个排列,一个排列也对应一个独特的中介数。通过中介数的顺序遍历(+1)便可不遗漏地得到所有的排列。
因为一个的数字的排列方式是唯一确定的,不需要中介数。故n个数的排列对应的中介数只有n-1位。
树图法
字典序法
中介数中的第i个数c1表示对应的排列中的第i个数字应该从剩下的数中取第i个(由小到大排序,从0开始编号)。如:
中介数:201
c1=2 表示排列的第一个数应取1,2,3,4中的3;
c2=0 表示排列的第二个数应取1,2,4中的1;
c3=1 表示排列的第三个数应取2,4中的4;
故中介数201对应的排列为3142;
中位数数位 |
c1 |
c2 |
c3 |
进制 |
4 |
3 |
2 |
位权 |
3*2 |
2 |
1 |
邻位对换法:
中介数的第i位决定了第i+1个数字在排列中的位置。中介数的该位对应的子树在此层排序的奇偶性决定了第i+1个数字插入原序列的方向。例:
中介数:102
初始数列:1
c1=1 表示排列中数字2应该插入当前数列“从后向前数”(默认方向)的1号空挡;
当前数列:21
c2=0 表示排列中数字3应该插入当前数列“从前向后数”(因为 c1=1 为奇数)的0号空挡;
当前数列:321
c3=2 表示排列中数字4应该插入当前数列“从前向后数”(因为 (c1c2)=1*3+0=3为奇数)的2号空挡;
当前数列:3241
中位数数位 |
c1 |
c2 |
c3 |
进制 |
2 |
3 |
4 |
位权 |
3*4 |
4 |
1 |
逆序法:
逆序:以递增数列作为参照对象(逆序为0),一个数列中若出现后面的数小于前面的数,则该数列的逆序数+1。如
1234的逆序数为1(逆序对:32)
4312的逆序数为5(逆序对:43,41,42,31,32)
对于数列
注意到,n在排列中的逆序数最多为n-1;n-1在排列中的逆序数最多为n-2;······;1在排列中的逆序数最多为0
故将2至n共n-1个数字的逆序数记录下来拼成一个中介数时,该中介数各个位的取值范围不同,即各位有不同的进制。由此产生了两种中介数组织方式:由低位到高位进制递增的称为“递增进位制数法”;由低位到高位进制递减的称为“递减进位制数法”。
递增进位制数法:
中介数的高位指示了待排数字中较大数的逆序数。例如:
中介数:201
c1=2 表示待排数字4的逆序数为2,故排列为X4XX;
c2=0 表示待排数字3的逆序数为0,故排列为X4X3;
c3=1 表示待排数字2的逆序数为2,故排列为24X3;
最终得排列2413
中位数数位 |
c1 |
c2 |
c3 |
进制 |
4 |
3 |
2 |
位权 |
3*2 |
2 |
1 |
递减进位制数法:
中介数的低位指示了待排数字中较大数的逆序数。例如:
中介数:102
c3=2 表示待排数字4的逆序数为2,故排列为X4XX;
c2=0 表示待排数字3的逆序数为0,故排列为X4X3;
c1=1 表示待排数字2的逆序数为2,故排列为24X3;
最终得排列2413
中位数数位 |
c1 |
c2 |
c3 |
进制 |
2 |
3 |
4 |
位权 |
3*4 |
4 |
1 |