数学基础 -- 线性代数之排列及其逆序数

排列及其逆序数

排列（Permutation）是指将一个有限集合的所有元素按照一定的顺序进行排列，每种不同的排列都称为该集合的一个排列。例如，集合 { 1 , 2 , 3 } \{1, 2, 3\} {1,2,3} 的所有排列为 $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(2,3,1)$、$(3,1,2)$、$(3,2,1)$。

逆序数

逆序数（Inversion Number）是排列中的一种度量方式，表示一个排列中，出现了多少对元素的相对顺序与它们在集合中的自然顺序相反。例如，对于排列 $(2,3,1)$，我们可以看到元素“2”比“1”大却排在“1”的前面，因此这对元素构成了一个逆序。同样，“3”比“1”大且也排在“1”的前面，因此它也是逆序的一对。因此，排列 $(2,3,1)$ 的逆序数为2。

如何计算逆序数

假设给定一个长度为 $n$ 的排列 $(a_1,a_2,\dots ,a_n)$，逆序数可以通过如下步骤计算：

1. 对于每个元素 $a_i$，找到后面所有比 $a_i$ 小的元素的个数。
2. 将所有这些个数相加，得到排列的逆序数。

举例说明

假设排列为 $(3,1,2)$，我们计算它的逆序数：

• 对于元素 3：后面比 3 小的元素有 1 和 2，共 2 个逆序。
• 对于元素 1：后面没有比 1 小的元素，所以没有逆序。
• 对于元素 2：后面没有比 2 小的元素，所以没有逆序。

因此，排列 $(3,1,2)$ 的逆序数为 2。

常见用途

逆序数的概念在算法和数据结构中有广泛应用，特别是在排序算法（如归并排序、快速排序）以及计算排列的奇偶性（确定排列是否是偶排列或奇排列）等问题中。