一个排列的分组问题
对于一个有n个不同数的构成的所有排列，可以将它们分为两组，分别属于这两个组的排列，其重合的部分不超过n-2个数，而在一个组中的任意两个排列其重合的部分不超过n-3个数。这两个组又可分别分为3组，不同组之内的排列其重合部分不超过n-3个数，而组内的两个排列重合部分不超过n-4个数，可以如此不断细分下去，直至分出的每一组内的任意两个排列没有任何部分重合。 两个排列的重合部分 是什么意思？比如 1 2 3 4 5和5 1 2 3 4，他们的重合部分是 0 还是 4 ？ 上面的重合部分为空集.也就是说位置相同且数值相同的数有几对。 可以根据逆序数的奇偶性可以把排列分成两组,进一步的分成3组可以用下面的方法.
对排列中相相邻的3个数,比如x1x2x3,我们可以做一个交换,使它变成x2x3x1,这里暂且称为C交换.
我们可以这样来定义一个关于排列的一个特征数t.
设初始数列为123...它的t值为0,而每对它其中相邻的3个数做C交换,设做交换的三个数开头那个数处在数列的第n位,当n为奇数时t的值就加1偶数就减1.
特征数t对3的模和过程是没有关系的,可以对两个排列规定一个由其中一个排列变化到另一个排列的标准程序.这个标准程序是这样的,比如对第一个排列数x1处在第n位,而在第2个排列中它刚好处在第1位,那么就对第1个排列进行一系列的交换,对第(n-1),n,(n+1)位上的数进行C交换,对(n-2),(n-1),n位上的数进行C交换,如此交换下去,直至数x1移动到第1位.接着假设第2个排列中第2位数是x2,那么用同样的方法把第1个数列中x2移动到第2位,如此进行下去直至两数列相同.由标准程序得到的t值和由其他过程得到的t值他们对3的模是相等的.
页:
[1]