通过编程来学习线性代数2-计算行列式的值

2018-05-30

全排列及其逆序数

为了计算每一项，我们先要了解如何生成每一个相乘的项，了解什么时候是正数什么时候是负数，关于正负问题就需要了解逆序数的定义。

全排列:

将n个不同的元素排成一列


1 > 1

2 > 1,2 | 2,1

3 > 1,2,3 | 1,3,2 | 2,1,3 | 2,3,1 | 3,1,2 | 3,2,1

...

从排列组合的知识中可以知道: n个不同的元素, 从中选取一个放到第一位, 有n钟选法, 剩下n-1个.

继续从这n-1各种继续选取, 放到第二位, 有n-1钟选法.

以此类推, 直到选完为止.

n个元素所有排列的种数: n! = n*(n-1)*...*3*2*1

这里我们用 Heap’s algorithm 描述的算法来生成所有的排列组合:

// Heap's algorithm

/**
 * 列举所有@param A 数组元素的全排列(排列)
 * 
 * @param {Number} n A长度
 * @param {Array} A 元素
 * @param {Array} result 全部结果
 */
function generate(n, A, result) {
    if (n == 1) {
        result.push(A.slice())
    }
    else {
        for (let i = 0; i < n - 1; i++) {
            generate(n - 1, A, result)
            if (n % 2 == 0) {
                swap(A, i, n - 1)
            }
            else {
                swap(A, 0, n - 1)
            }
        }
        generate(n - 1, A, result)
    }
}

可以在浏览器的控制台中试一下, 如generate(3, [1, 2, 3], arr)或者generate(4, ['a', 'b', 'c', 'd'], arr), 字符数字都行，arr需要事先定义好let arr = []

控制台测试

得到每一项后, 就可以进行计算逆序数了. 一个排列的逆序数决定了这一项是正或负数.

逆序：

n个不同的自然数，规定从小到大为标准次序。当某两个元素的先后次序与标准次序不同时，就称这两个元素组成一个逆序

逆序数：

排列中所有逆序的总数称为此排列的逆序数

计算逆序数的方法，我是直接从第一个开始，依次跟剩下的进行对比：

function calcInverseNumber(item) {
    let sum = 0
    for (let i = 0, len = item.length; i < len; i++) {
        // 取出第i个数
        let digit = item[i]
        // 用第i个数与第i位之后的数进行对比
        for (let j = i + 1; j < len; j++) {
            if (digit > item[j]) {
                sum++
            }
        }
    }
    return sum
}

到这里，生成计算中的每一项和计算每一项的逆序数的方法都有了，接下来就需要一个计算方法。这个计算方法需要传入一个行列式，然后通过generate生成相乘的每一项，再通过calcInverseNumber算出每一项的逆序数来判断该项的正负值，最终各项相加得出结果。

在计算每一项的值时，元aij中的i的值不变，相乘的j取n的排列。如三阶行列式的计算：

其中每三个相乘中，三个元的i角标都是1,2,3，j角标取全排列每一项的值。

// 计算行列式的值
/**
 * @param {Array} data 行列式数组
 * 
 */
function calcDeterminantV1(data) {
    let n = data.length
    let standardIndex = []
    for (let i = 0; i < n; i++) {
        standardIndex.push(i)
    }

    let indexArr = []
    generate(n, standardIndex, indexArr)

    let sum = 0
    for (let i = 0, len = factorial(n); i < len; i++) {
        let arr = indexArr[i]
        let inverseCount = calcInverseNumber(arr)

        let item = (inverseCount % 2 ? -1 : 1)
        for (let j = 0; j < n; j++) {
            item *= data[j][arr[j]]
        }
        sum += item
    }

    return sum
}

line 7 获取行列式的长度
line 8-11 生成一个标准排列的数组[0, 1, 2, ..., n-1]
line 13-14 生成0~n-1的所有可能的排列，共n!个，indexArr有n!个长度为n的数组，这些数组的元素是0~n-1组成的一个排列。
line 16-26 计算行列式data的值，函数factorial(n)为计算n!的值。
line 17-24遍历indexArr数组，计算每个排列的值。
line 19计算排列arr的逆序数，line 21判断逆序数inverseCount的正负（奇数为负，偶数为正）。
line 22-25 使data中角标(j, arr[j])对应的数进行相乘，得到item，并追加到总数sum中。

函数factorial(n):

/**
 * 
 * @param {Number} n 
 */
function factorial(n) {
    var result = 1
    for (i = 2; i <= n; i++) {
        result *= i
    }
    return result
}

现在可以试试用这个方法来计算行列式的值了，比如：

[[1, 0, 0],
[0, 3, 0],
[0, 0, 3]]
// sum = 9

[[1, 2, -4],
[-2, 2, 1],
[-3, 4, -2]]
// sum = -14

[[2, 1, -5, 1],
[1, -3, 0, -6],
[0, 2, -1, 2],
[1, 4, -7, 6]]
// sum = 27

目前，计算行列式的值已经告一段落了，下一节将实现一些行列式的延伸。

比如行列式按行（列）展开相关知识。

代码

tomfriwel/linearAlgebraPro

声明：转载请注明作者及原文链接

数学

全排列及其逆序数

代码