当前位置：文档之家 › 组合数学排列的逆序生成算法

组合数学排列的逆序生成算法

  • 格式：pdf
  • 大小：379.39 KB
  • 文档页数：4

证明2（构造算法2）
从n个空位开始，从左至右标为1,2,…,n。 1：由于排列中有个b1整数在1前面，将1放在b1+1位置。 2：在排列中要有b2个比2大的数在2的前面，2的位置便根据 b2可以确定(注意，1占用的位置不算空位）； … K:在排列中要有bk个比k大的数在k的前面，k的位置便根据bk 可以确定(应排除已被占用的位置，只数空位) … n:n放在最后的空位中。
排列中的逆序
• 设i1i2…in是[1,n]的一个排列，如果k<l,ik>il ,则数对 称为一个逆序。例如，31524有4个逆序对。 • 对于一个排列， aj= 在排列中先于 j 且大于 j 的整数 的个数；它量度 j 的反序的程度。例如， 31524 的 逆序列是：1 2 0 1 0。 • 注意，逆序列满足条件： 0≤a1≤n-1,0≤a2≤n-2,…,0 ≤an-1≤1,an=0
这是因为k,在[1,n]中存在n-k个数比k大。由乘法原理， 满足0≤b1≤n-1,0≤b2≤n-2,…,0 ≤bn-1≤1,bn=0的b1,b2,…,bn序 列有n· (n-1)· …· 2· 1=n!个。即逆序列个数与排列的个数 一样多。
定理：令b1,b2,…,bn 是满足0≤b1≤n-1,0≤b2≤n-2,…,0 ≤bn-1≤1,bn=0的整数序列，则存在[1,n]的唯一排列， 其逆序53402110生成排列。
算法1： 逆序：5 3 4 0 2 1 1 0 bj : 12345678 8 87 867 8657 48657 486537 4862537 48625137 算法2： 逆序：5 3 4 0 2 1 1 0 bj : 12345678 _____1__ ___2_1__ ___2_13_ 4__2_13_ 4__2513_ 4_62513_ 4_625137 48625137
证明1：从逆序列构造排列算法1 n:写出n. n-1:考虑bn-1（介于0，1），若bn-1=0，则n-1在n前，否则在 n后。 n-2: bn-2 =0,1,2分别表示n-2应在n,n-1的前，中，后。 … n-k: bn-k =0,1,…,k表示在n,n-1,…n-k+1几个数中插入n-k的位 置在第几个。 …… 1：我们必须把1放在步骤n-1所构造的序列的第b1 个数的后 面。 这样就等到相应的排列。

合集下载

线性代数排列及其逆序数

线性代数排列及其逆序数

第11页/共13页
计算法的本质：
• 本质为计算排列中的每一元与其前面的 元所产生的逆序数，然后逐个相加，即 得排列的逆序数。各种方法的区别在于 计算排列中每一元的逆序数的顺序，第 一种方法是按元本身从小到大计算，而 第二种方法是按元后在的位置从右往左 计算。
第12页/共13页
感谢您的观看！
第13页/共13页
2m 1次相邻对换 a1 al bb1 bmac1 cn ,
所以一个排列中的任意两个元素对换，排列改变 奇偶性.
第9页/共13页
推论 奇排列调成标准排列的对换次数为奇数， 偶排列调成标准排列的对换次数为偶数.
定理2 在全部 n 阶排列中 n 2,奇偶排列各
占一半.
第10页/共13页
四、小结
1 n 个不同的元素的所有排列种数为 n!. 2 排列具有奇偶性. 3 计算排列逆序数常用的方法有多种. 4 对换改变排列的奇偶性.
第4页/共13页
排列的奇偶性 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列.
第5页/共13页
三、对换
定义
在排列中，将任意两个元素对调，其余 元素不动，这种作出新排列的手续叫做 对换．
将相邻两个元素对调，叫做相邻对换． 例如
a1 al a bb b1 bm a1ala b1bm b c1cn a1 al bbaa b1 bm a1al b b1bm aa c1cn
第6页/共13页
对换与排列的奇偶性的关系
定理1 一个排列中的任意两个元素对换，排列 改变奇偶性． 证明 设排列为
a1al ab b1bm 对换a与b a1al bbaa b1bm 除a ,b 外，其它元素的逆序a 的逆序数增加1 , b 的逆序数不变; 当a b时， 经对换后 a 的逆序数不变 ，b的逆序数减少1.
行列式计算逆序数公式

行列式计算逆序数公式

行列式计算逆序数公式
行列式计算逆序数公式（Inversion Formula）是一种数论算法，它可以用来计算任何n阶行列式中每个元素逆序数（inverse order）的总和。

换句话说，行列式计算逆序数公式可以计算一个n阶行列式中每一个元素都可以有多少种不同的逆序数组合。

它也被称为“row sums of X”（行列式的行和）。

具体来讲，行列式计算逆序数的公式由两部分组成：
第一部分是机器可以直接识别的数学公式，用于表示每一个元素的逆序数。

比如，一个3阶行列式的元素的逆序数可以用数学公式简写成(Inversion of the element)= Inversion (A[x, y]) = x + y + 1，其中x+y+1是每一个元素逆序数的值。

第二部分就是利用上述公式来实现行列式计算逆序数的正则表达式，即把逆序数的公式结果乘以全局的行列表乘积。

也就是说，行列式中的每一个元素都可以利用第一部分的公式来确定其逆序数等于x+y+1。

然后再用第二部分的正则表达式来计算所有逆序数的总和。

总之，行列式计算逆序数公式是一种数论算法，它利用直接识别的数学公式，以及正则表达式来表示每一个元素可以有多少种不同的逆序数组合，从而计算行列式中所有元素的逆序数总和。

第二节 排列及其逆序数

第二节 排列及其逆序数

例如 排列32514 中， 0 01
32514
1 逆序数为3
故此排列的逆序数为3+1+0+1+0=5.
记做 (3 2 514) 5
排列的奇偶性 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 例如，在123组成的全排列中，有3个偶排列123， 231，312；有三个奇排列132，213，321 ❖一般说来，n 个数的全排列中，奇偶排列各占一半。
第二排列及其逆序数
1 全排列 2 排列的逆序数 3 逆序数的计算方法
问题 把 n 个不同的元素排成一列，共有几种不 同的排法？
定义1
把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（简称排列）.
n 个不同的元素的所有排列的种数，通 常用 Pn 表示.
例如 P3 3 2 1 6.
同理 Pn n (n 1) (n 2) 3 2 1 n!.
32514 5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3; 4的前面比4大的数有1个,故逆序数为1;
32514 01 031 于是排列32514的逆序数为
0 1 0 3 1 5. (从头开始法)
例2 计算下列排列的逆序数，并讨论它们的奇 偶性.
1 217986354
分别计算出排列中每个元素前面比它大的数码 个数之和，即从排列中第一个元素开始，依次 算出排列中每个元素的逆序数，这每个元素的 逆序数之总和即为所求排列的逆序数.（从“头” 开始法） 例1 求排列32514的逆序数.
解 在排列32514中,
3排在首位,逆序数为0;
2的前面比2大的数只有一个3,故逆序数为1;
我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准排列（自然 排列）.
12全排列和对换

12全排列和对换

13
作业：
P21 习题一 2.(2)(4)(5)(6)
14
kg2k [1 (2k 1)]gk k 2,
2
当 k 为偶数时，排列为偶排列，
当 k 为奇数时，排列为奇排列.
8
2 2k12k 122k 232k 3L k 1k
解 2k 1 2k 1 2 2k 2 3 2k 3 k 1 k
2
二、全排列的逆序数
先规定一个标准次序.
如自然次序： 1 2 3 4 L (n 1) n
逆序：两个元素的次序与标准次序不同，就说有
1个逆序. 逆序数：排列中所有逆序的总数. n 6时， 12 3456 ---标准次序
偶排列： 14 2 356 ---有 2 个逆序
42
逆序数
43
奇排列： 3 21456 ---有 3 个逆序
t 0 1 0 0 1 3 4 4 5 18. (2) n (n 1) (n 2) L 3 2 1
0 1 2 L n3 n2 n1
t 0 1 2 L (n 3) (n 2) (n 1) n(n 1) . 2
21
31
32
3
逆序数的计算方法
方法1 分别计算出排列中每个元素前面比它大的元素 个数之和，即算出排列中每个元素的逆序数，它们 之总和即为所求排列的逆序数.
例1 求排列32514的逆序数.
解
32514
0 1 031
于是排列32514的逆序数为
t 0 1 0 3 1 5.
4
方法2
分别计算出排在 1,2, … n-1 的位置上的数后面比 它小的数码之和，即分别算出 1,2, … n-1 这 n-1