найти уникальные матрицы из большей матрицы

Question

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

01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Простой.Просто проведите пальцем вниз, один за другим в группах по 3, чтобы получить что-то похожее на:

01 02 03 | 02 03 04 | 03 04 05 | 06 07 08
06 07 08 | 07 08 09 | 08 09 10 | 11 12 13
11 12 13 | 12 13 14 | 13 14 15 | 16 17 18

или, в Scala,

List(List(1, 2, 3), List(6, 7, 8), List(11, 12, 13))
List(List(2, 3, 4), List(7, 8, 9), List(12, 13, 14))
List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15))
List(List(6, 7, 8), List(11, 12, 13), List(16, 17, 18))

и так далее, и так далеена ...

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

val array2D = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25".grouped(3).map(_.trim.toInt).grouped(5)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

Теперь у меня есть структура данных, с которой я могу работать, но я не вижу функционального пути. Конечно, я могу пройти через каждый фрагмент sliced, создать var matrix = new ListBuffer[Seq[Int]]() и обязательно создать пакет из них, и я 'м готово.

Я хочу найти функциональный, в идеале бессмысленный подход с использованием Scala, но я в замешательстве. Должен быть способ застегнуть на 3 или что-то подобное... Я искал ScalaDocs и не могу понять это.

Answer 1

Вы попали на полпути туда.На самом деле, мне было трудно понять, как сделать то, что ты уже сделал.Я немного разбил твой код, чтобы было легче следовать.Кроме того, я сделал array2D a List, чтобы мне было проще играть с кодом.: -)

val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D = (intArray grouped 5 toList)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

Итак, у вас есть несколько списков, каждый из которых похож на этот:

List(List(List( 1,  2,  3), List( 2,  3,  4), List( 3,  4,  5)), 
     List(List( 6,  7,  8), List( 7,  8,  9), List( 8,  9, 10)), 
     List(List(11, 12, 13), List(12, 13, 14), List(13, 14, 15)))

И вы хотите, чтобы они были такими:

List(List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13)), 
     List(List(2, 3, 4), List(7, 8,  9), List(12, 13, 14)), 
     List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15)))

Это тебе кажется правильным?Каждый из трех подсписков - это отдельная матрица:

List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13))

- это

01 02 03
06 07 08
11 12 13

Итак, в основном, вы хотите транспонировать их.Следующий шаг:

val subMatrices = sliced map (_.transpose)

Тип этой вещи List[List[List[Seq[Int]]]].Давайте рассмотрим немного ... 2D матрица представлена ​​последовательностью последовательности, поэтому List[Seq[Int]] соответствует матрице.Скажем:

type Matrix = Seq[Seq[Int]]
val subMatrices: List[List[Matrix]] = sliced map (_.transpose)

Но вам нужен один список матриц, поэтому вы можете сгладить это:

type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = (sliced map (_.transpose) flatten)

Но, увы, map плюс flatten - этоa flatMap:

type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)

Теперь вам нужны уникальные подматрицы.Это достаточно просто: это набор.

val uniqueSubMatrices = subMatrices.toSet

Или, если вы хотите сохранить результат в виде последовательности,

val uniqueSubMatrices = subMatrices.distinct

И все.Полный код, чтобы проиллюстрировать:

type Matrix = Seq[Seq[Int]]
val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D: Matrix = (intArray grouped 5 toList)
val sliced: List[List[Matrix]] = (array2D map (row => row sliding 3 toList) sliding 3 toList)
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)
val uniqueSubMatrices: Set[Matrix] = subMatrices.toSet

Его можно записать как одно выражение, но если вы не разбите его на функции, читать его будет ужасно.И вам придется либо использовать прямой канал (|>, а не в стандартной библиотеке), либо неявно добавить эти функции к типам, на которые они действуют, иначе все равно будет трудно читать.

Answer 2

Редактировать: Хорошо, я думаю, я наконец понял, что вы хотите. Я собираюсь показать способ, который работает, а не способ, который высокопроизводителен. (Как правило, это изменчивое Java-подобное решение, но вы уже знаете, как это сделать.)

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

Но, ладно, давайте все равно это сделаем.

val big = (1 to 25).grouped(5).map(_.toList).toList

Это вся матрица, которую вы хотите. Далее

val smaller = (for (r <- big.sliding(3)) yield r.toList).toList

- это группы строк, которые вы хотите. Теперь вы должны были использовать 2D-структуру данных, потому что вы хотите сделать что-то, что плохо отображается на одномерные операции. Но:

val small = smaller.map(xss =>
  Iterator.iterate(xss.map(_.sliding(3)))(identity).
    takeWhile(_.forall(_.hasNext)).
    map(_.map(_.next)).
    toList
).toList

Если вы аккуратно разберете это, вы увидите, что вы создаете группу итераторов (xss.map(_.sliding(3))), а затем перебираете их все в шаге блокировки, удерживая эти итераторы шаг за шагом, останавливаясь, по крайней мере, один из них пуст и отображает их на следующие значения (как вы идете с ними вперед).

Теперь, когда у вас есть матрицы, вы можете хранить их по своему усмотрению. Лично я бы сгладил список:

val flattened = small.flatten

Вы написали структуру, имеющую матрицы рядом, что вы также можете сделать с некоторым усилием (опять же, потому что создание 2D-операций из 1D-операций не всегда просто):

val sidebyside = flattened.reduceRight((l,r) => (l,r).zipped.map(_ ::: _))

(обратите внимание на lowerRight, чтобы сделать эту операцию O (n) вместо O (n ^ 2) - присоединение к концу длинных накопительных списков - плохая идея - но также обратите внимание, что при слишком большом количестве матриц это, вероятно, переполнить стек).