Skip to content

Instantly share code, notes, and snippets.

@jimka2001
Created February 23, 2024 14:07
Show Gist options
  • Save jimka2001/fca66f10e8c04bd4732c9153bce7b5e2 to your computer and use it in GitHub Desktop.
Save jimka2001/fca66f10e8c04bd4732c9153bce7b5e2 to your computer and use it in GitHub Desktop.
(ns homework.determinant)
(defn supress_rc
"Given a function, f (as returned from mat-to-function or from supress_rc).
Assuming f can be called with indices 0 <= r < n and 0 <= c < n,
return a new function which can be called on 0 <= r < n-1 and 0 <= c < n,
which will skip the row and column specified omit-r and omit-c"
[f omit-r omit-c]
(fn [r0 c0]
(f (if (< r0 omit-r) r0 (inc r0))
(if (< c0 omit-c) c0 (inc c0)))))
(defn mat-to-function
"Convert a matrix, i.e. a vector of vectors of numbers into a function
which can be called with the row and column index (zero-based) to extract
the entry from the matrix."
[mat]
(assert (vector? mat))
(assert (< 0 (count mat)) (format "%s expected to have size > 0" mat))
(assert (every? vector? mat)) ;; is mat a vector of vectors
(assert (every? (fn [row] ;; all of the same length, ie a square matrix
(= (count mat) (count row))) mat))
(fn [r0 c0]
((mat r0) c0)))
(defn determinant
"Compute the determinant of a square matrix (dim >= 1)
using the Laplacian expansion. This has n! complexity."
[mat]
(letfn [(det [dim f]
(if (= 1 dim)
(f 0 0)
(reduce +
0
(pmap (fn [k]
(if (= 0 (f 0 k))
;; if (f 0 k) is 0, no need to recure
0
(* (if (even? k) 1 -1)
(f 0 k)
(det (dec dim)
(supress_rc f 0 k)))))
(range dim)))))]
(det (count mat)
(mat-to-function mat))))
;;; some tests
(determinant [[1]])
(determinant [[1 0]
[0 1]])
(determinant [[1 0 0]
[0 1 0]
[0 0 1]])
(determinant [[1 2 3]
[4 5 6]
[7 8 9]])
(determinant [[1 2 3 1]
[4 4 6 2]
[4 5 6 3]
[7 8 9 4]])
(determinant [[1 2 3 1 1]
[4 4 6 2 1]
[4 4 6 2 2]
[4 5 6 3 1]
[7 8 9 4 1]])
(determinant [[1 0 3 1 1 1]
[4 4 6 2 1 2]
[4 4 6 2 2 1]
[4 4 6 2 2 2]
[4 5 6 3 1 1]
[7 8 9 4 1 2]])
(determinant [[1 0 3 1 1 1 0]
[4 4 6 2 1 2 2]
[4 4 6 2 1 2 1]
[4 4 6 2 2 1 2]
[4 4 6 2 2 2 2]
[4 5 6 3 1 1 1]
[7 8 9 4 1 2 3]])
(determinant [[1 1 0 3 1 1 1 0]
[4 2 4 6 2 1 2 2]
[4 4 3 6 2 1 2 1]
[4 4 6 4 2 2 1 2]
[4 4 6 2 5 2 1 2]
[4 4 6 2 2 6 2 2]
[4 5 6 3 1 1 7 1]
[7 8 9 4 1 2 3 8]])
(determinant [[1 0 1 0 3 1 1 1 0]
[4 2 0 4 6 2 1 2 2]
[4 4 3 0 6 2 1 2 1]
[4 4 6 4 0 2 2 1 2]
[4 4 6 4 2 0 2 1 2]
[4 4 6 2 5 2 0 1 2]
[4 4 6 2 2 6 2 0 2]
[4 5 6 3 1 1 7 1 0]
[0 7 8 9 4 1 2 3 8]])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment