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

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, но я в тупике. Там должен быть способ сделать zip с 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 является 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, потому что вы хотите сделать что-то, что плохо отображено на 1D-операции. Но:

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(_ ::: _)) 

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