Упорядочение 2D-массива

Question

Я пытаюсь решить проблему с двумерными массивами и мне не нужна помощь. Проблема выглядит так:

Предположим, у нас есть двумерный массив A размером nxn, состоящий из уникальных элементов. Необходимо переставить элементы А следующим образом. Пусть A11, A12, A21, A22 - четыре непересекающихся подмассива матрицы A, каждый размером n / 2 x n / 2. Тогда A11

Ввод пользователя: n, N (≥ n2). n является степенью 2

Я пробовал много вещей, но ничего не получается.

Answer 1

В какой-то мере воспользовавшись ответом unkulunkulu, я думаю, вы могли бы подойти к нему следующим образом:

Возьмите все значения в вашей матрице (2D) и поместите их в простой массив (1D). Затем возьмите этот массив и отсортируйте значения по возрастанию.

Теперь вам нужно снова заполнить матрицу, но таким образом, чтобы она соответствовала указанным вами правилам. Если вы посмотрите на кривую заполнения пространства Z-порядка в 2D , вы обнаружите, что если вы заполните матрицу в этом порядке (с отсортированными элементами), то полученная матрица будет иметь желаемые свойства.

Теперь на самом деле кодирование будет за вами.

Answer 2

В главе 21.8 http://www.nrbook.com/nr3/ из книги «Числовые рецепты» дано аналитическое выражение для расчета индекса в двумерный массив с учетом координат дерева квадрантов.

Вот еще один прямой подход, который я попробовал, но мне он не очень нравится:

(defun quad-pos (pos)
  "POS is a list of letters that indicate the position in a 2x2 matrix [a,b; c,d]."
  (let ((x 0)
    (y 0)
    (s 1))
    (dolist (e pos)
      (setf s (/ s 2))
      (ecase e
    ('a )
    ('b (incf x s))
    ('c (incf y s))
    ('d (incf x s) (incf y s))))
    (values x y)))
#+nil
(quad-pos '(a)) ;=> 0, 0
#+nil
(quad-pos '(a b c)) ;=> 1/4, 1/8
#+nil
(quad-pos '(d d d d)) ;=> 15/16, 15/16

Answer 3

Вам необходимо создать функцию, которая будет преобразовывать индекс между 0 и n * n-1 в координаты в вашем массиве в соответствии с рассматриваемым порядком.Затем вы просто запускаете какой-то обычный алгоритм 1D-сортировки для массива размером n * n, j-й элемент которого заменяется с помощью этой функции.Это решает проблему.

Обновление: функция отображения отображает числа в этой матрице в их координаты:

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