Пролог получи квадраты матрицы NxN

Question

У меня есть список L = [[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]] Ii.Это представляет мою матрицу.Размер может изменяться динамически, поэтому размер блока может быть разным, 4x4 = 4 элемента, 9x9 = 9 элементов

Я хочу получить 4 квадрата, составляющих список. (В данном случае это матрица 4 на 4).Если у меня есть эта матрица:

5  6  7  8
10 11 12 13
1  2  3  4
14 15 16 17 

Результат должен быть:

R = [5,6,10,11],[7,8,12,13],[1,2,14,15],[3,4,16,17].

Любые предложения приветствуются.Спасибо

Answer 1

Первое, что вам нужно, это действительно рычаг для превращения списка списков в матрицу.Чем отличается двумерная матрица от списка списков?Идея системы координат.Так что вам нужен способ связать пару координат с соответствующим значением в матрице.

at(Matrix, X, Y, V) :- nth0(X, Matrix, Row), nth0(Y, Row, V).

Этот предикат позволяет индексировать матрицу в (X, Y) и получатьзначение V. Это, IMO, массивная демонстрация того, что делает Пролог мощным, потому что, получив этот простой предикат, вы получаете:

• Возможность получитьзначение в предоставленной точке:

  ?- at([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], 1,3, V).
  V = 13.
  

• Возможность повторять всю матрицу (только создать экземпляр Matrix и оставить другие аргументы в качестве переменных):

  ?- at([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], X,Y, V).
  X = Y, Y = 0,
  V = 5 ;
  X = 0,
  Y = 1,
  V = 6 ;
  ...
  X = 3,
  Y = 2,
  V = 16 ;
  X = Y, Y = 3,
  V = 17.
  

• Возможность поиска в матрице значений:

  ?- at([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], X,Y, 14).
  X = 3,
  Y = 0 ;
  false.
  

Так что это довольно полезный рычаг!В традиционном языке для выполнения всех этих задач вам понадобятся три разные функции, но это не так, потому что в Prolog нам просто нужно определить отношение между вещами (в данном случае структуру данных ипара координат) и Пролог может сделать довольно много тяжелой работы.

Теперь легко увидеть, как мы можем создать конкретную подматрицу, просто определив наборы значений X и Y, которые мы хотели быувидеть.Например, чтобы получить верхнюю левую матрицу, мы должны сделать это:

?- between(0,1,X), between(0,1,Y), 
   at([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], X,Y, V).
X = Y, Y = 0,
V = 5 ;
X = 0,
Y = 1,
V = 6 ;
X = 1,
Y = 0,
V = 10 ;
X = Y, Y = 1,
V = 11.

Конечно, мы можем использовать findall/3, чтобы собрать решения в одном месте:

?- findall(V, (between(0,1,X), between(0,1,Y), 
               at([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], X,Y, V)),
           Vs).
Vs = [5, 6, 10, 11].

То, что осталось для вашей проблемы - это в основном некоторая арифметика.Посмотрим, есть ли у нас квадратная матрица:

square_matrix(M, Degree) :-
    length(M, Degree),
    maplist(length, M, InnerDegrees),
    forall(member(I, InnerDegrees), I=Degree).

Это не идеальный предикат, поскольку он не будет генерироваться!Но он скажет нам, является ли матрица квадратной, и если да, то в какой степени она имеет:

?- square_matrix([[5,6,7,8],[10,11,12,13],[1,2,3,4],[14,15,16,17]], D).
D = 4.

После того, как вы это сделаете, вам нужно что-то вроде формулы:

1. Убедитесь, что степень является идеальным квадратом
2. Возьмите квадратный корень из степени.Вот сколько у вас строк или столбцов (квадратный корень 4 = 2, 2 строки и 2 столбца, квадратный корень 9 = 3, 3 строки и 3 столбца).
3. Создайте отношение междукоординаты (строка, столбец) и список (x, y) координат для матрицы в этом месте.Например, в матрице 4x4 у вас есть четыре плитки: (0,0), (0,1), (1,0) и (1,1).Координаты для (0,0) будут (0,0), (0,1), (1,0), (1,1), но координаты для (1,1) будут (2,2), (2,3), (3,2), (3,3).Если вы сделаете несколько из них вручную, вы увидите, что это будет равносильно добавлению смещения x и y ко всем перестановкам от 0 до количества строк / столбцов (минус одна) для обеих координат.
4. Теперь, когда у вас есть эти отношения, вам нужно выполнить итерацию и собрать ваш вывод.Я думаю maplist/N будет достаточно для этого.

Надеюсь, это поможет!