Как лучше хранить квадратные матрицы и находить в них подматрицы?

@Vaderkos · Регистрация: 31.03.2015

Студворк — интернет-сервис помощи студентам

Как лучше хранить квадратную матрицу, если в ней нужно будет находить подматрицы по координатам и суммы элементов этих матриц?
У меня вариант такой

Lisp
1
2
3
4
5
;; Изначально хранить матрицу вот так пр. 4х4
( (0 0 0 0)
  (0 0 0 0)
  (0 0 0 0)
  (0 0 0 0) )

А для подматриц создать структуру

Lisp
1
(defstruct abstract matrix sum)

Не знаю правда как найти подматрицу. Должно быть как-то так

Координаты 0 0 2 1
(0 0 0 0)
(0 0 0 0)
(0 0 0 0)
(0 0 0 0)

@Catstail · 02.01.2016, 23:37

В CL лучше использовать двумерные массивы (без затей).

@Vaderkos · 02.01.2016, 23:46 **[ТС]**

Catstail,

Сообщение от Vaderkos

как найти подматрицу

Этот вопрос меня больше волнует

@Catstail · 02.01.2016, 23:50

А если на списках, то можно, например, так:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
;; Вырезка из матрицы matr прямоугольной матрицы
;; на пересечении строк из списка r-list и столбцов из списка c-list
 
(defun cut-matrix (matr r-list c-list)
  (let ((a nil)
        (b nil)
        (res nil))
    (iter (for r in matr) (for i upfrom 0)
        (when (member i r-list) (collecting r into a)))
    (iter (for r in a)
        (setq b nil)
        (iter (for p in r) (for i upfrom 0)
          (when (member i c-list) (collecting p into b)))
        (collecting b into res))))
 
(cut-matrix '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)) '(0 1) '(0 1))
 
==> ((1 2) (5 6))
 
(cut-matrix '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)) '(0 1) '(1 2))
 
==> ((2 3) (6 7))
 
(cut-matrix '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)) '(0 1) '(1 2 3))
 
==> ((2 3 4) (6 7 8))

@vlisp · 03.01.2016, 00:11

Сообщение от Vaderkos

Этот вопрос меня больше волнует

вырезка кусков матрицы от краев

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(nthcdr
  1
  (mapcar
   '(lambda (x) (nthcdr 2 x))
   '((0 1 2 3)
     (1 1 2 3)
     (2 2 4 6)
     (3 3 6 9)))
)
 
(butlast
  (mapcar
   '(lambda (x) (butlast x 2))
   '((0 1 2 3)
     (1 1 2 3)
     (2 2 4 6)
     (3 3 6 9)))
 1)

@helter · 03.01.2016, 00:20

Может, подматрицу вообще не нужно выделять? Если предположить, что подматрица «помнит» своего родителя (то есть, математически говоря, рассматривать пары (A', A), где A' — подматрица A), то реализовать подматрицу можно просто как совокупность матрицы и номеров строк и столбцов, на пересечении которых она стоит. Плюс (или минус) такого подхода в том, что, например, в матрице
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}<br /> 0 & 0 \\<br /> 0 & 0<br /> \end{pmatrix}$
различаюся четыре подматрицы первого порядка, хотя если их рассматривать как матрицы, она только одна — нулевая.

Если говорить о реализации этой идеи в CL — например, так: матрица — двумерный массив, подматрица — структура из матрицы плюс два бит-вектора, так что подматрица образована пересечением строк и столбцов, для номеров которых в бит-векторах стоит 1.

Добавлено через 2 минуты
Базовое API может состоять из функций s/rows, s/columns, s/aref, возвращающих число строк, столбцов и элемент подматрицы соответственно.

@_sg · 03.01.2016, 10:41

для списков:

Lisp
1
2
3
4
5
6
7
8
(defun sub-matrix (w n m j k)
  (loop for c in (loop for a in w for b from 0
                       when (<= n b m) collect a)
        collect (loop for d in c for e from 0
                      when (<= j e k) collect d)))
 
> (sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 1 3 2 3)
((6 7) (10 11) (14 15))

@Catstail · 03.01.2016, 10:53

_sg, ну да, те же три цикла.

@_sg · 03.01.2016, 11:21

Lisp
1
2
3
4
5
6
7
8
(defun sub-matrix (w n m j k)
  (loop for a in w for b from 0
        when (<= n b m)
        collect (loop for d in a for e from 0
                      when (<= j e k) collect d)))
 
> (sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 1 3 2 3)
((6 7) (10 11) (14 15))

@Vaderkos · 03.01.2016, 12:55 **[ТС]**

Кстати, числа из подматриц не обязательно хранить матрицой, их можно хранить просто списком

Сообщение от _sg

(sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 1 3 2 3)
((6 7) (10 11) (14 15))

Можно возвращать в таком виде

Lisp
1
(6 7 10 11 14 15)

, да и порядок тут не важен.

@_sg · 03.01.2016, 13:09

Lisp
1
2
3
4
5
6
7
8
(defun sub-matrix (w n m j k)
  (loop for a in w for b from 0
        when (<= n b m)
        nconc (loop for d in a for e from 0
                    when (<= j e k) collect d)))
 
> (sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 1 3 2 3)
(6 7 10 11 14 15)

@Vaderkos · 03.01.2016, 13:23 **[ТС]**

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

Добавлено через 1 минуту
И ещё, я не совсем понимаю разницу между массивами и списками в лиспе. Масиив имеет фиксированный размер? Или как?

Добавлено через 10 минут
_sg, Помоему не работает.

Lisp
1
2
3
4
5
6
7
8
9
(setf x '((1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4)))
 
((1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4))
* x
 
((1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4))
* (sub-matrix x 0 0 2 1)
 
NIL

@_sg · 03.01.2016, 13:42

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun sub-matrix (w n m j k)
  (loop for a in w for b from 0
        when (<= n b m)
        nconc (loop for d in a for e from 0
                    when (<= j e k) collect d)))
 
(defun sub-mx (w n m)
  (loop for a in w for b from 0
        when (<= n b m) collect a))
 
> (sub-mx '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 0 0)
((0 1 2 3))
> (sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 0 0 1 2)
(1 2)

Добавлено через 44 секунды

Сообщение от Vaderkos

не совсем понимаю разницу между массивами и списками в лиспе

http://lisper.ru/pcl/pcl.pdf - с. 118

@Vaderkos · 03.01.2016, 14:04 **[ТС]**

_sg, Теперь понял, то же самое что и в С++ или Джаве. Тогда наверно лучше использовать их в этой задачи. Я думаю матрица будет выглядеть вот так.

Lisp
1
2
3
#(#(1 2 3)
   #(1 2 3)
   #(1 2 3) )

Добавлено через 8 минут
Catstail, Я понял о чем вы, то есть что-то такое

Lisp
1
(make-array '(4 4))

А как найти в них подматрицу?

@_sg · 03.01.2016, 14:12

Lisp
1
2
3
4
5
6
7
8
(defun sub-matrix (w n m j k)
  (loop for a across w for b from 0
        when (<= n b m)
        nconc (loop for d across a for e from 0
                    when (<= j e k) collect d)))
 
> (sub-matrix #(#(0 1 2 3) #(4 5 6 7) #(8 9 10 11) #(12 13 14 15)) 1 3 2 3)
(6 7 10 11 14 15)

Добавлено через 2 минуты

Lisp
1
2
3
4
5
6
7
8
9
(defun sub-matrix (w n m j k)
  (apply #'vector
         (loop for a across w for b from 0
               when (<= n b m)
               nconc (loop for d across a for e from 0
                           when (<= j e k) collect d))))
 
> (sub-matrix #(#(0 1 2 3) #(4 5 6 7) #(8 9 10 11) #(12 13 14 15)) 1 3 2 3)
#(6 7 10 11 14 15)

@Vaderkos · 03.01.2016, 14:24 **[ТС]**

_sg, я не понимаю как у вас расположены координаты, если брать 1 3 2 3, то должно выйти

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Добавлено через 1 минуту
А чем отличается такой двумерный массив от такого

Lisp
1
2
#2A((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15))
#(#(0 1 2 3) #(4 5 6 7) #(8 9 10 11) #(12 13 14 15))

@_sg · 03.01.2016, 23:18

массивы:

http://rosettacode.org/wiki/As... ommon_Lisp

http://rosettacode.org/wiki/Re... ommon_Lisp

http://rosettacode.org/wiki/Arrays#Common_Lisp

http://rosettacode.org/wiki/Ar... ommon_Lisp

матрицы:

http://rosettacode.org/wiki/Ma... ommon_Lisp

http://rosettacode.org/wiki/Ma... ommon_Lisp

http://rosettacode.org/wiki/Ma... ommon_Lisp

@Vaderkos · 04.01.2016, 00:07 **[ТС]**

_sg, Вообще, мне и обычной

Lisp
1
#2A((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15))

Хватает, я написал уже для задания большую часть функций, осталась только нахождение подматрицы по координатам
и подсчет одинкаовых элементов в списке

Добавлено через 20 минут
Уже все написал, осталась эта функция, если б я хотя бы алгоритм понимал(

@_sg · 04.01.2016, 07:57

Lisp
1
2
3
4
5
6
7
8
9
10
(defun sub-matrix (w n j m k)
  (loop for a in w for b from 0
        when (<= n b m)
        nconc (loop for d in a for e from 0
                    when (<= j e k) collect d)))
 
> (sub-matrix '((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15)) 1 3 2 3)
(7 11)
> (sub-matrix '((0 1 2) (3 4 5) (6 7 8)) 0 0 1 2)
(0 1 2 3 4 5)

Lisp
1
2
3
4
5
6
(defun counter (w)
  (loop for a in (remove-duplicates w) 
        collect (list a (count a w))))
 
> (counter '(a b b c c c))
((A 1) (B 2) (C 3))

@Vaderkos · 04.01.2016, 15:12 **[ТС]**

_sg, А как такое провернуть с двумерным массивом

Lisp
1
#2A((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15))

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,708 Записей в блоге: 14
	02.01.2016, 23:37
	В CL лучше использовать двумерные массивы (без затей). 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	03.01.2016, 00:20
	Может, подматрицу вообще не нужно выделять? Если предположить, что подматрица «помнит» своего родителя (то есть, математически говоря, рассматривать пары (A', A), где A' — подматрица A), то реализовать подматрицу можно просто как совокупность матрицы и номеров строк и столбцов, на пересечении которых она стоит. Плюс (или минус) такого подхода в том, что, например, в матрице $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}<br /> 0 & 0 \\<br /> 0 & 0<br /> \end{pmatrix}$ различаюся четыре подматрицы первого порядка, хотя если их рассматривать как матрицы, она только одна — нулевая. Если говорить о реализации этой идеи в CL — например, так: матрица — двумерный массив, подматрица — структура из матрицы плюс два бит-вектора, так что подматрица образована пересечением строк и столбцов, для номеров которых в бит-векторах стоит 1. Добавлено через 2 минуты Базовое API может состоять из функций s/rows, s/columns, s/aref, возвращающих число строк, столбцов и элемент подматрицы соответственно. 1

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,708 Записей в блоге: 14
	03.01.2016, 10:53
	_sg, ну да, те же три цикла. 0

@_sg 4709 / 4404 / 380 Регистрация: 12.05.2012 Сообщений: 3,101
	03.01.2016, 23:18
	массивы: http://rosettacode.org/wiki/As... ommon_Lisp http://rosettacode.org/wiki/Re... ommon_Lisp http://rosettacode.org/wiki/Arrays#Common_Lisp http://rosettacode.org/wiki/Ar... ommon_Lisp матрицы: http://rosettacode.org/wiki/Ma... ommon_Lisp http://rosettacode.org/wiki/Ma... ommon_Lisp http://rosettacode.org/wiki/Ma... ommon_Lisp 1