逆序数 | 玄数

2018-06-01

逆序数

把n个不同的元素排成一列,叫做这n个元素的全排列Pn,共有n!种不同的排法。在任一排列中,某两个元素排列的次序是前大后小时,就产生了1个逆序。一个排列中所有逆序的总数叫做这个排列的逆序数。逆序数为奇数的排列叫做奇排列,逆序数为偶数的排列叫做偶排列

求逆序数有两种方法:

  1.  在前面,把比当前数大的个数累加
  2.  在后面,把比当前数小的个数累加

如:52143

第一种方法:

  • 5:第1个数,不需要计算,τ1 = 0
  • 2:前面比2大的有1个( 5 ) ,τ2 = 1
  • 1:前面比1大的有2个( 5, 2 ) ,τ3 = 2
  • 4:前面比4大的有1个( 5 ) ,τ4 = 1
  • 3:前面比3大的有2个( 5, 4) ,τ5 = 2

所以逆序总和为:τ= 0 + 1 + 2 + 1 + 2 = 6

第二种方法:

  • 5:后面比5小的有4个( 2, 1, 4, 3 ),τ1 = 4
  • 2:后面比2小的有1个( 1 ) ,τ2 = 1
  • 1:后面比1小的有0个,τ3 = 0
  • 4:后面比4小的有1个( 3 ),τ4 = 1
  • 3:最后1个数,不需要计算,τ5 = 0

所以逆序总和为:τ= 4 + 1 + 0 + 1 + 0 = 6

 

行列式

定义:把n2个数排成n行n列的数表,得n阶行列式,记作
determinants

(更多…)