8000 feat: add determinant algorithm · TheAlgorithms/TypeScript@ef5b88b · GitHub
[go: up one dir, main page]
Skip to content

Commit ef5b88b

Browse files
cosmicproccosmicproc
committed
feat: add determinant algorithm
1 parent 19b4ced commit ef5b88b

File tree

2 files changed

+143
-0
lines changed
  • maths
    • < 8000 div class="PRIVATE_TreeView-item-container prc-TreeView-TreeViewItemContainer--2Rkn" style="--level:2">
      determinant.ts
  • test

    • 2 files changed

    +143
    -0
    lines changed

    ‎maths/determinant.ts

    Lines changed: 54 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -0,0 +1,54 @@
    1+
    /**
    2+
    * @function det
    3+
    * @description
    4+
    * Computes the determinant of the given matrix using elimination.
    5+
    * - Rounding errors may occur for some matrices.
    6+
    * - Only handles 6 decimal places. Rounds thereafter.
    7+
    * @Complexity_Analysis
    8+
    * Time complexity: O(n^3)
    9+
    * Space Complexity: O(n^2)
    10+
    * @param {number[][]} m - A square matrix (2D array)
    11+
    * @return {number} - The determinant
    12+
    * @example det([[1,1],[1,1]]) = 0
    13+
    */
    14+
    15+
    export function det(m: number[][]): number {
    16+
    if (m.some((r) => r.length != m.length)) {
    17+
    throw new Error('only square matrices can have determinants')
    18+
    }
    19+
    20+
    const decPlaces = 6
    21+
    22+
    // track the number of applied interchange operations
    23+
    let appliedICs = 0
    24+
    for (let i = 0; i < m[0].length; i++) {
    25+
    // partial pivotting
    26+
    let idealPivot = -1
    27+
    let maxValue = 0
    28+
    for (let j = i; j < m.length; j++) {
    29+
    if (Math.abs(m[j][i]) > maxValue) {
    30+
    maxValue = Math.abs(m[j][i])
    31+
    idealPivot = j
    32+
    }
    33+
    }
    34+
    if (idealPivot === -1) {
    35+
    return 0
    36+
    }
    37+
    if (idealPivot != i) {
    38+
    appliedICs++
    39+
    ;[m[i], m[idealPivot]] = [m[idealPivot], m[i]]
    40+
    }
    41+
    // eliminate entries under the pivot
    42+
    for (let j = i + 1; j < m.length; j++) {
    43+
    if (Math.abs(m[j][i]) > 1 / 10 ** decPlaces) {
    44+
    m[j] = m[j].map((e, k) => e + (-m[j][i] / m[i][i]) * m[i][k])
    45+
    }
    46+
    }
    47+
    }
    48+
    let diagProduct = 1
    49+
    for (let i = 0; i < m.length; i++) {
    50+
    diagProduct *= m[i][i]
    51+
    }
    52+
    let result = diagProduct * (-1) ** appliedICs
    53+
    return parseFloat(result.toFixed(decPlaces))
    54+
    }

    ‎maths/test/determinant.test.ts

    Lines changed: 89 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -0,0 +1,89 @@
    1+
    import { det } from '../determinant'
    2+
    3+
    describe('determinant', () => {
    4+
    test.each([
    5+
    [
    6+
    [
    7+
    [1, 2],
    8+
    [3, 4, 5]
    9+
    ]
    10+
    ],
    11+
    [
    12+
    [
    13+
    [1, 2, 3],
    14+
    [4, 5, 6]
    15+
    ]
    16+
    ],
    17+
    [
    18+
    [
    19+
    [1, 2],
    20+
    [3, 4],
    21+
    [5, 6]
    22+
    ]
    23+
    ]
    24+
    ])('should throw an error for non square matrix %p', (matrix) => {
    25+
    expect(() => det(matrix)).toThrow(
    26+
    'only square matrices can have determinants'
    27+
    )
    28+
    })
    29+
    30+
    test.each([
    31+
    [
    32+
    [
    33+
    [1, 2],
    34+
    [3, 4]
    35+
    ],
    36+
    -2
    37+
    ],
    38+
    [
    39+
    [
    40+
    [1, 1],
    41+
    [1, 1]
    42+
    ],
    43+
    0
    44+
    ],
    45+
    [
    46+
    [
    47+
    [1, 2],
    48+
    [0, 0]
    49+
    ],
    50+
    0
    51+
    ],
    52+
    [
    53+
    [
    54+
    [8, 1, 5],
    55+
    [9, 3, 7],
    56+
    [1, 4, 4]
    57+
    ],
    58+
    8
    59+
    ],
    60+
    [
    61+
    [
    62+
    [15, 85, 32],
    63+
    [76, 83, 23],
    64+
    [28, 56, 92]
    65+
    ],
    66+
    -382536
    67+
    ],
    68+
    [
    69+
    [
    70+
    [2, -1, 0, 3],
    71+
    [4, 0, 1, 2],
    72+
    [3, 2, -1, 1],
    73+
    [1, 3, 2, -2]
    74+
    ],
    75+
    -42
    76+
    ],
    77+
    [
    78+
    [
    79+
    [0.75483643, 0.68517541, 0.53548329, 0.5931435],
    80+
    [0.37031247, 0.80103707, 0.82563949, 0.91266224],
    81+
    [0.39293451, 0.27228353, 0.54093836, 0.51963319],
    82+
    [0.60997323, 0.40161682, 0.58330774, 0.17392144]
    83+
    ],
    84+
    -0.051073
    85+
    ]
    86+
    ])('determinant of %p should be %d', (matrix, expected) => {
    87+
    expect(det(matrix)).toBe(expected)
    88+
    })
    89+
    })

    0 commit comments

    Comments
     (0)
    0