encontre matrizes únicas de uma matriz maior

Question

Eu sou bastante novo na programação funcional, então estou fazendo alguns exercícios práticos. Eu quero escrever uma função, dada uma matriz de naturais únicos, digamos 5x5, retornar uma coleção de matrizes únicas de um tamanho menor, digamos 3x3, onde as matrizes devem estar intactas, ou seja, criadas a partir de valores adjacentes ao original.

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

Simples. Basta deslizar e descer, um a um em grupos de 3, para obter algo parecido com:

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

ou, em 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))

e assim por diante ...

Então, eu me aventuro com Scala (minha linguagem de escolha porque me permite evoluir de imperativo para funcional, e passei os últimos anos em 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

Agora tenho uma estrutura de dados com a qual posso trabalhar, mas não vejo uma maneira funcional. Claro que posso percorrer cada pedaço do sliced, criar um var matrix = new ListBuffer[Seq[Int]]() e, obrigatoriamente, criar um pacote deles e pronto.

Quero encontrar uma abordagem funcional e idealmente sem pontos usando Scala, mas estou perplexo. Deve haver uma maneira de zipar com 3 ou algo assim ... Eu pesquisei nos ScalaDocs e não consigo descobrir.

Answer 1

Você chegou na metade do caminho. Na verdade, eu estava tendo problemas para descobrir como fazer o que você já tinha feito. Eu quebrei um pouco o seu código para torná-lo mais fácil de seguir. Além disso, tornei array2D um List, para poder brincar com o código mais facilmente. :-)

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

Ok, então você tem um monte de listas, cada uma um pouco assim:

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)))

E você os quer assim:

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)))

Parece certo para você? Cada uma das três sublistas é uma matriz própria:

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

é

01 02 03
06 07 08
11 12 13

Então, basicamente, você deseja transpô-los. A próxima etapa, então, é:

val subMatrices = sliced map (_.transpose)

O tipo dessa coisa é List[List[List[Seq[Int]]]]. Vamos considerar que um pouco ... A matriz 2D é representada por uma sequência de uma sequência, então List[Seq[Int]] corresponde a uma matriz. Digamos:

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

Mas você quer uma lista única de matrizes, então pode achatar isso:

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

Mas, infelizmente, um map mais um flatten é um flatMap:

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

Agora, você quer as submatrizes exclusivas. Isso é bastante simples: é um conjunto.

val uniqueSubMatrices = subMatrices.toSet

Ou, se você deseja manter o resultado em uma sequência,

val uniqueSubMatrices = subMatrices.distinct

E é isso. Código completo apenas para ilustrar:

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

Pode ser escrito como uma única expressão, mas a menos que você divida em funções, vai ser horrível de ler. E você teria que usar o canal de encaminhamento (|>, não na biblioteca padrão) ou adicionar essas funções implicitamente aos tipos em que atuam, ou será difícil de ler de qualquer maneira.

Answer 2

Editar: Ok, acho que finalmente entendi o que você quer. Vou mostrar uma forma que funciona, não uma forma de alto desempenho. (Essa é geralmente a solução mutável semelhante ao Java, mas você já sabe como fazer isso.)

Primeiro, você realmente deve fazer isso com suas próprias coleções que funcionam em 2D de maneira sensata. Usar um monte de coleções 1D para emular coleções 2D vai levar a confusão e complicações desnecessárias. Não faça isso. Mesmo. É uma má ideia.

Mas, ok, vamos fazer assim mesmo.

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

Esta é toda a matriz que você deseja. A seguir,

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

são os grupos de linhas que você deseja. Agora, você deveria estar usando uma estrutura de dados 2D, porque deseja fazer algo que não mapeia bem em operações 1D. Mas:

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

Se você separar isso cuidadosamente, verá que está criando um monte de iteradores (xss.map(_.sliding(3))) e, em seguida, iterando todos eles na etapa de bloqueio, mantendo os mesmos iteradores passo a passo, parando quando pelo menos um dos eles estão vazios e mapeando-os em seus próximos valores (que é como você os acompanha).

Agora que você tem as matrizes, pode armazená-las como quiser. Pessoalmente, eu simplificaria a lista:

val flattened = small.flatten

Você escreveu uma estrutura que tem as matrizes lado a lado, o que também pode ser feito com algum esforço (novamente, porque criar operações 2D a partir de operações 1D nem sempre é simples):

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

(observe a redução à direita para tornar esta operação O (n) em vez de O (n ^ 2) - juntar-se ao final de longas listas acumuladas é uma má ideia - mas observe também que com muitas matrizes isso provavelmente será transbordar a pilha).