Симметричный 2-мерный массив - PullRequest
Новая
       6

Симметричный 2-мерный массив

3 голосов
/ 12 февраля 2012

Каким будет код для проверки, является ли массив двумерным?Для одного измерения я знаю, что обратный список будет работать.Для двухмерных я знаю, что противоположная строка / столбец должны быть одинаковыми.Другими словами [1] [2] должно равняться [2] [1] и так далее.

(defun симметричная проверка (список) (равный список (обратный список)))

Ответы [ 3 ]

3 голосов
/ 12 февраля 2012

Прежде всего реализация матрицы с использованием списка списков неэффективна, если вам нужен произвольный доступ, потому что это будет стоить O(n + m) вместо более дешевого O(1) с использованием двумерного массива.

Чтобы проверить симметрию, прежде всего убедитесь, что матрица квадратная, а затем вам просто нужно проверить, что элемент m_ij равен элементу m_ji для всех пар.

Так как вам нужно проверить все пары на симметрию, имеет смысл рассмотреть только i > j, чтобы не выполнять каждый тест дважды (>, а не >=, потому что явно m_ii равен самому себе).

В качестве дополнительного бонуса проверка на симметрию не требует учета основных диагональных элементов. 

(defun symmetric (m)
  (let ((rows (array-dimension m 0))
        (cols (array-dimension m 1)))
    (when (= rows cols)
      (dotimes (i rows T)
        (dotimes (j i)
          (unless (= (aref m i j) (aref m j i))
            (return-from symmetric NIL)))))))

(let ((m (make-array (list 5 5) :initial-element 0)))
  (dotimes (i 5)
    (dotimes (j 5)
      (setf (aref m i j) (* (1+ i) (1+ j)))))
  (print m)
  (print (symmetric m))
  (setf (aref m 3 2) 9)
  (print m)
  (print (symmetric m)))
2 голосов
/ 12 февраля 2012

Это зависит от вашего определения симметрии.

В линейной алгебре матрица называется симметричной, если она равна ее транспонированию (это эквивалентно тому, что M [i, j] = M [j, i] для всех я и j ). Таким образом, 

(defun matrix-symmetric-p (m)
  (equal m (transpose-matrix m)))

(defun transpose-matrix (m)
  ;; implement this
  ...)

Я настоятельно рекомендую использовать настоящие массивы, потому что это сделает выполнение таких вещей проще и намного более эффективным. 

(defun matrix-symmetric-p (m)
  (loop for i from 0 below (array-dimension m 0)
        always
          (loop for j from 0 below (array-dimension m 1)
                always
                  (= (aref m i j) (aref m j i)))))
1 голос
/ 12 февраля 2012

Тем не менее, название нечеткое, учитывая ваш пример, аналог, вероятно, будет следующим: 

(defun symmetric-2d-list-p (list)
  (equal (reverse (mapcar #'reverse list)) list))

(symmetric-2d-list-p '((1 1 1) (2 2) (3) (2 2) (1 1 1))) ; T
(symmetric-2d-list-p '((2 1 2) (2 2) (3) (2 2) (2 1 2))) ; T
(symmetric-2d-list-p '((1 1 1) (2 2) (3 4) (2 2) (1 1 1))) ; NIL

Но вы действительно хотите уточнить, потому что двумерные массивы - это совершенно разные вещи, тогда списки, содержащие списки.

Возможно, это лучший ответ, который не требует создания дополнительных списков. Я действительно сделал это так из-за вашего оригинального примера. Надеюсь, кто-то опубликует более оптимальную версию.

...