排列的逆序数

对于一个排列，如果是从到到尾都是从小到大，那么逆序数(number of permutation inversions)就为0.只要出现一次大的在前，小的在后，逆序数就加一次。逆序数的符号是希腊字母 $\tau$ ,读音为“涛",比如以下排列：
$3, 6, 5, 4, 1, 2$
它的逆序数是多少呢？把逆序对，写出来：
$(3,1),(3,2)\\ (6,5),(6,4),(6,1),(6,2)\\ (5,4),(5,1),(5,2)\\ (4,1),(4,2)\\$
所以逆序数为
$\tau(3,6,5,4,1,2)=11$
逆序数为奇数就是奇排列，逆序数为偶数就是偶排列。

行列式定义

行列式的定义是一个求和，求和的每一项是从矩阵的按顺序从每一列找出不同行的元素连乘起来，他们的行号如果是奇排列就乘以-1，如果是偶排列就不变。行列式的符号是一对竖线，跟绝对值一样，或者用det表示，用数学语言就是这样表示：
$|A|=det(A)=\sum(-1)^{\tau(i_1,\cdots,i_j,\cdots,i_n)}\prod_{j=1}^{n}a_{i_jj}$
比如计算三阶矩阵的行列式，就是这样的：
$|A_|=det(A)\\=\tau(1,2,3)a_{11}a_{22}a_{33}+\\ \tau(1,3,2)a_{11}a_{32}a_{23}+\\ \tau(2,1,3)a_{21}a_{12}a_{33}+\\ \tau(2,3,1)a_{21}a_{32}a_{13}+\\ \tau(3,1,2)a_{31}a_{12}a_{23}+\\ \tau(3,2,1)a_{31}a_{22}a_{13}\\= a_{11}a_{22}a_{33}\\ -a_{11}a_{32}a_{23}\\ -a_{21}a_{12}a_{33}\\ +a_{21}a_{32}a_{13}\\ +a_{31}a_{12}a_{23}\\ -a_{31}a_{22}a_{13}$
当然也可以按顺序从每行找不同列的元素相乘，结果都是一样的，上面的公式就可以改写为：
$|A|=det(A)=\sum(-1)^{\tau(j_1,\cdots,j_i,\cdots,j_n)}\prod_{i=1}^{n}a_{ij_i}$

Python实现

按照定义计算行列式，需要求全排列，我在求全排列时，使用了Heap算法，至于Heap算法，可以参考我的博文：全排列Heap算法。全排列求出来了的话，剩余的就简单了，代码如下：

python">    def determinant_by_permutation(self):
        import com.youngthing.mathalgorithm.permutations.heap as hp
        n = len(self.__vectors)
        array = [i for i in range(n)]
        permutations = hp.permutations(array)
        sum = 0
        for p in permutations:
            inversions = hp.number_of_inversions(p)
            item = 1
            for i in range(n):
                item *= self.__vectors[i][p[i]]
            if (inversions & 1) == 0:
                sum += item
            else:
                sum -= item
        return sum

测试数据：
$\begin{vmatrix}1 & -1 & -2 & -3\\ 3 & 2 & 1 & 4\\ 2 & 1 & 1 & 1\\ 6 & 5 & 4 & 3\\ \end{vmatrix}=-28$
对于算法基础不好的人来说，求全排列确实麻烦，所以我接下来要介绍一种递归到 $2\times 2$ 矩阵的行列式算法，实现起来比较容易，链接如下：Chiò算法。