Симметричный двумерный массив

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

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


lisp common-lisp
person Tequila    schedule 12.02.2012    source источник
comment
Массив: (setf arr (сделать-массив '(2 2): начальное содержимое' ((1 2) (2 3))))   -  person Tequila    schedule 12.02.2012

Ответы (3)


arrow_upward
2
arrow_downward

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

В линейной алгебре матрица называется симметричной тогда и только тогда, когда она равна своей транспонированной (это эквивалентно тому, что M[i, j] = M[j, i] для всех i< /em> и 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)))))
person Matthias Benkard    schedule 12.02.2012
comment
Для неквадратной матрицы этот код даст сбой... также вы проверяете каждую пару дважды. Зачем использовать loop, даже если его синтаксис на самом деле более многословен, чем lispier dotimes? - person 6502; 12.02.2012
comment
@ 6502 Верно, но определение симметрии, которое я использовал, в любом случае не имеет смысла для неквадратной матрицы. dotimes потребовало бы использования чего-то вроде block и return-from (обратите внимание, что я использовал директиву always) и, следовательно, семантически было бы немного уродливее. - person Matthias Benkard; 12.02.2012
comment
Я провел реальный массив через необходимый мне тест, и он сработал. Спасибо, - person Tequila; 12.02.2012

arrow_upward
3
arrow_downward

Прежде всего, реализация матрицы с использованием списка списков неэффективна, если вам нужен произвольный доступ, потому что это будет стоить 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)))
person 6502    schedule 12.02.2012

arrow_upward
1
arrow_downward

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

(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

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

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

person Community    schedule 12.02.2012