gistfile1.txt

(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]])