Finding number of saddle points of a matrix
Posted: Tue Feb 21, 2012 5:12 am
Hi, I've encountered this question, and I thought it would be interesting to try to solve it with the least complexity. So far I only have a fair naive solution with the complexity being O(2 * x * y), but it looks like it should be possible to reduce it - yet I cannot find a good way to do it.
For the reference, saddle point is a value in the matrix, which is at the same time the smallest value in its row and the greatest value in it's column.
Code: Select all
(defun saddle-points-naive (matrix)
(let* ((x (array-dimension matrix 0))
(y (array-dimension matrix 1))
(mins (make-array x))
(maxs (make-array y))
(element)
(total 0))
(dotimes (i x)
(dotimes (j y)
(setf element (aref matrix i j)
(aref maxs j)
(if (zerop i)
element
(max element (aref maxs j)))
(aref mins i)
(if (zerop j)
element
(min element (aref mins i))))))
(dotimes (i x total)
(dotimes (j y)
(when (= (aref maxs i)
(aref mins j)
(aref matrix i j))
(incf total))))))
(defparameter *random-matrix*
(let ((m (make-array '(5 5))))
(dotimes (z 25 m)
(setf (aref m (floor (/ z 5)) (mod z 5))
(random 25)))))
(defparameter *flat-matrix*
(make-array '(3 3) :initial-element 1))
(defparameter *parabolic-matrix*
(make-array '(5 5)
:initial-contents
'((5 3 0 3 5)
(7 5 3 5 7)
(9 7 5 7 9)
(7 5 3 5 7)
(5 3 0 3 5))))
(saddle-points-naive *random-matrix*)
(saddle-points-naive *flat-matrix*)
(saddle-points-naive *parabolic-matrix*)