逆序对与交换

逆序对与交换

$\hspace{1cm}$一些非常基础的性质。约定一个排列是形如1,3,2,4这样的数列。

• 对任意一个排列，交换其两个数的位置，对逆序对造成的变化量的值都是奇数。

  设两个要交换的数分别是 $\varphi$ 和 $\theta$，他们中间夹着$a_1, a_2, a_3, … ,a_n$，也就是形如：
  $$
  \varphi, a_1, a_2, a_3, .., a_n, \theta
  $$
  因为我们关心的是逆序对的变化量，所以和逆序对变化量有关的逆序对中至少有一方得是$\varphi$或$\theta$，且两方都在$\varphi, a_1, a_2, ..,a_n, \theta$这个序列内部。

  先考虑$\varphi < \theta$的情况：

  设$a_1, a_2, … ,a_n$中有$x$个数小于$\varphi$，有$y$个数大于$\varphi$小于$\theta$，则有$n-x-y$个数大于$\theta$。

  交换之前，和$\theta$、$\varphi$两者中至少一方有关的逆序对个数为$x + n - x - y = n - y$。

  交换之后，和$\theta$、$\varphi$两者中至少一方有关的逆序对个数为$x + y + n - x + 1 = n + y + 1$

  因此变化量为$2y + 1$，为奇数。

  再考虑$\varphi > \theta$的情况：

  设$a_1, a_2, … ,a_n$中有$x$个数小于$\theta$，有$y$个数大于$\theta$小于$\varphi$，则有$n-x-y$个数大于$\varphi$。

  交换之前，和$\theta$、$\varphi$两者中至少一方有关的逆序对个数为$x + y + y + n - x - y + 1 = n + y+ 1$。

  交换之后，和$\theta$、$\varphi$两者中至少一方有关的逆序对个数为$x+ n - x - y = n - y$

  因此变化量为$-2y - 1$，为奇数。

​

• 如果只通过交换元素位置的方式，将一个排列变换为另外一个排列，那么需要交换的次数的奇偶性和两个排列的逆序对的差值的奇偶性相同。

  有上面那个定理之后，这个就非常明晰了。每次交换对逆序对造成的变化量的值都是奇数，因此每次交换都会改变逆序对数量的奇偶性。如果前后两个排列的逆序对的奇偶性相同，那么交换的次数必定是偶数次。反之，如果前后两个排列的逆序对的奇偶性不同，那么交换的次数必定是奇数次。