逆序数及其应用

刷手机的时候看到一个逆序数的算法题，刚好又在复习矩阵论，行列式里也有用到逆序数，想到大二时学的逆序数计算算法，回顾了一下，并写下这篇文章记录。
1. 定义

假设有一个排列\(a_1,a_2,\dots,a_n\)，如果下标对\(\langle i,j \rangle\)满足\(i \lt j\)而\(a_i > a_j\)，就称有序对\(\langle a_i, a_j \rangle\)是一个逆序对。排列中，所有逆序对的数量称为逆序数。
例如：排列\(3,1,2\)中的逆序对为\(\langle 3, 1 \rangle\)和\(\langle 3, 2 \rangle\)，逆序数为\(2\)。
可以看出，逆序数为\(0\)的排列是单调递增的，单调递减排列的逆序数最大。
2. 逆序数的计算

逆序数一般通过归并排序（即分治算法）或树状数组计算，此处只讲解归并排序解法。
将问题进行分解：将数组从中点划分为左右两个子数组，求数组的逆序数就转换为求左子数组的逆序数\(i_l\)、右子数组的逆序数\(i_r\)以及左子数组相对右子数组的逆序数\(i_{lr}\)（即逆序对第一个元素来自左子数组，第二个来自右子数组）。求左右子数组的逆序数均可再次进行分解，直至子数组仅包含\(1\)个或\(2\)个元素。子数组仅包含\(1\)个元素时，逆序数为\(0\)；子数组仅包含\(2\)个元素\(a,b\)时，\(a \le b\)时逆序数为\(0\)，否则为\(1\)。因此重点在于求解左子数组相对右子数组的逆序数\(i_{lr}\)。
可以发现，任意改变左子数组的元素顺序，以及任意改变右子数组的元素顺序，都不会影响\(i_{lr}\)。假设左右子数组都是单调递增的，那么对于左子数组中的元素\(a_i\)以及右子数组中的元素\(b_j\)，如果\(a_i\)和\(b_j\)构成逆序对，那么\(a_i\)之后的元素\(a_{i+1}, a_{i+2}, \dots, a_{l}\)都能和\(b_j\)构成逆序对。

证明：\(a_i\)和\(b_j\)构成逆序对，说明\(a_i \gt b_j\)。而左子数组单调递增，即\(\forall k \gt 0, a_{i+k} \ge a_i\)，因此有\(a_{i+k} \gt b_j\)。

由此，可以得到以下计算\(i_{lr}\)的算法：

1. Algorithm CountCrossInversions(left[0..l-1], right[0..r-1]):
2.         Input:
3.         left: 左子数组，长度为l，单调递增
4.         right: 右子数组，长度为r，单调递增
5.     Output:
6.         左子数组相对右子数组的逆序数
8.     i ← 0
9.     j ← 0
10.     result ← 0
12.     while i < l and j < r do
13.         if left[i] > right[j] then
14.             result ← result + (l - i)
15.             j ← j + 1
16.         else
17.             i ← i + 1
18.         end if
19.     end while
21.     return result

复制代码

归并排序将数组从中点划分为两个子数组，分别对子数组再次进行归并排序，再合并两个有序数组，实现排序。以上计算\(i_{lr}\)的算法和归并排序合并有序子数组的过程高度相似，并且左右子数组都需要提前进行排序，因此只需对归并排序合并有序子数组的操作稍作修改即可计算数组的逆序数。
力扣LCR 170. 交易逆序对的总数即为逆序数计算的题目，具体的C++实现如下：

1. class Solution {
2. private:
3.     int mergeSort(vector<int>& record, int l, int r) {
4.         // 边界，子数组仅有1个元素
5.         if (l == r - 1)
6.             return 0;
7.         // 边界，子数组仅有2个元素
8.         if (l == r - 2) {
9.             if (record[l] > record[l + 1]) {
10.                 swap(record[l], record[l + 1]);
11.                 return 1;
12.             }
13.             return 0;
14.         }
16.         // 拆分为两个子问题
17.         int mid = l + (r - l) / 2;
18.         int i_l = mergeSort(record, l, mid);
19.         int i_r = mergeSort(record, mid, r);
21.         // 合并两个有序子数组，并计算左子数组相对右子数组的逆序数
22.         vector<int> temp(r - l);
23.         int i = 0, j = l, k = mid;
24.         int i_lr = 0;
25.         while (j < mid && k < r) {
26.             if (record[j] > record[k]) {
27.                 i_lr += mid - j; // record[j]及之后的元素，均能和record[k]构成逆序对
28.                 temp[i++] = record[k++];
29.             } else {
30.                 temp[i++] = record[j++];
31.             }
32.         }
33.         while (j < mid)
34.             temp[i++] = record[j++];
35.         while (k < r)
36.             temp[i++] = record[k++];
37.         copy(temp.begin(), temp.end(), record.begin() + l);
39.         return i_l + i_r + i_lr;
40.     }
41. public:
42.     int reversePairs(vector<int>& record) {
43.         if (record.empty())
44.             return 0;
45.         return mergeSort(record, 0, static_cast<int>(record.size()));
46.     }
47. };

复制代码

3. 逆序数的应用

3.1 最小相邻交换次数

算法题除了直接指明要计算逆序数外，还会以等价的问题——排序时最少需要多少次相邻交换的形式考察。该类问题的定义如下：
给定数组A，要将它变成单调递增序列，限制每次只能交换相邻的两个元素，至少需要多少次交换？（插入排序、冒泡排序等“邻近交换”的排序算法，都是这样操作的。）
最小的交换次数即为排列的逆序数。单调递增序列的逆序数为\(0\)，对于给定的排列，每次相邻交换最多减少\(1\)个逆序对，且在逆序数不为\(0\)时，总能进行一次相邻交换，使得逆序对减少。
单调递增序列的逆序数为\(0\)，由逆序对定义可以得到该结论。
对于给定的排列，每次相邻交换最多减少\(1\)个逆序对。因为是相邻交换，每次只能改变操作的两个元素之间的相对顺序，而其他元素相对这两个元素的顺序不会改变，因此只能使得逆序数加\(1\)（交换前不构成逆序对，且两个元素不断）、减\(1\)（交换前构成逆序对）或不变（两个元素相等）。
在逆序数不为\(0\)时，总能进行一次相邻交换，使得逆序对减少。假如不能通过相邻交换使逆序对减少，说明\(\forall a_i, a_i \le a_{i+1}\)，即排列单调递增，逆序数必为\(0\)。
3.2 Kendall tau距离

两个序列\(\tau _{1},\tau _{2}\)，长度相等，含有的元素相同但顺序不同，它们之间的Kendall tau距离定义如下：

\({\displaystyle K_{d}(\tau _{1},\tau _{2})=|\{(i,j):i\tau _{1}(j)\wedge \tau _{2}(i)