从更大的矩阵中找到唯一的矩阵 [英] find unique matrices from a larger matrix

问题描述

我是功能性编程的新手，所以我正在进行一些练习练习。我想写一个函数，给定一个独特的自然矩阵，让我们说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中，

 列表（列表（1，2，3），列表（6，7，8），列表（11，12，13））
 List（List（2，列表（3，4，5），列表（7，8，9），列表（12,13,14））
列表（列表（3,4,5），列表（8,9,10），列表（13 ，14,15））
列表（列表（6,7,8），列表（11,12,13），列表（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 
  
现在我有一个可以使用的数据结构，但是我没有看到一个功能方式。当然，我可以遍历每个切片的 code>，创建一个 var matrix = new List缓冲区[Seq [Int]]（）并且必须创建一个包并且完成。
 
 
 
我想找到一个<功能强大，理想的无点方法使用Scala，但我很难过。有一种方法来压缩3或类似的东西...我搜索了ScalaDocs，似乎无法弄清楚。
解决方案
你到了那里。事实上，我很难搞清楚如何去做你已经做过的事情。我分解了一下你的代码，使它更容易遵循。另外，我做了 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 =（输入拆分map（_.toInt）toList）
 val array2D =（intArray分组5到列表）
 val sliced = array2D.map （row => row.sliding（3，1）.toList）.sliding（3,1）.toList 
  
 
 $ b $ 
 列表（列表（列表）列表（1，2，3），列表（2,3,4），列表（3,4,5）），
列表（列表（6,7,8），列表（7,8,9） ，列表（8,9,10）），
列表（列表（11,12,13），列表（12,13,14），列表（13,14,15）））
  
而且您希望他们这样： 
 
 
  List（List（List（1，2，3），List（6，7，8），List（11，12，13）），
 List（List（2，3，4， ），列表（7,8,9），列表（12,13,14）），
列表（列表（3,4,5），列表（8,9,10），列表（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 
  
因此，基本上，您想转置它们。接下来的步骤是：
 
 $ $ $ $ $ $ $ $ $ $ $ $> $ sub $子类型=切片图（_.transpose）
  

这个东西的类型是 List [List [List [Seq [Int]]]] 。让我们考虑这一点...二维矩阵由一个序列序列表示，所以 List [Seq [Int]] 对应于一个矩阵。假设：

  type Matrix = Seq [Seq [Int]] 
 val subMatrices：List [List [Matrix] ] =切片图（_.transpose）
  

但是你想要一个矩阵列表，所以你可以flatten：

  type Matrix = Seq [Seq [Int]] 
 val subMatrices：List [Matrix] =（切片图（_.transpose）变平）
  

但是，唉，一张地图加上 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 =（输入拆分map（_.toInt）toList）
 val array2D ：Matrix =（intArray group 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 
  

可以将它写成单个表达式，但除非将其分解为函数，否则阅读起来会非常糟糕。而且你必须使用前向管道（ |> ，而不是在标准库中），或者将这些函数隐式添加到它们所作用的类型，或者它反正很难阅读。

I'm fairly new the functional programming, so I'm going through some practice exercises. I want to write a function, given a matrix of unique naturals, let's say 5x5, return a collection of unique matrices of a smaller size, say 3x3, where the matrices must be intact, i.e. created from values that are adjacent in the 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

Simple. Just slide across, then down, one by one in groups of 3, to get something that looks like:

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

or, in 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))

and so on and so on...

So I venture out with Scala (my language of choice because it allows me to evolve from imperative to functional, and I've spent the last few years in 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

Now I have a data structure I can work with, but I don't see a functional way. Sure I can traverse each piece of sliced, create a var matrix = new ListBuffer[Seq[Int]]() and imperatively create a bag of those and I'm done.

I want to find a functional, ideally point-free approach using Scala, but I'm stumped. There's got to be a way to zip with 3 or something like that... I've searched the ScalaDocs and can't seem to figure it out.

解决方案

You got halfway there. In fact, I was having trouble figuring out how to do what you had done already. I broke up your code a bit to make it easier to follow. Also, I made array2D a List, so I could play with the code more easily. :-)

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, so you have a bunch of lists, each one a bit like this:

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

And you want them like this:

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

Does that feel right to you? Each of the three sublists is a matrix on its own:

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

is

01 02 03
06 07 08
11 12 13

So, basically, you want to transpose them. The next step, then, is:

val subMatrices = sliced map (_.transpose)

The type of that thing is List[List[List[Seq[Int]]]]. Let's consider that a bit... The 2D matrix is represented by a sequence of a sequence, so List[Seq[Int]] corresponds to a matrix. Let's say:

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

But you want one one list of matrices, so you can flatten that:

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

But, alas, a map plus a flatten is a flatMap:

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

Now, you want the unique submatrices. That's simple enough: it's a set.

val uniqueSubMatrices = subMatrices.toSet

Or, if you wish to keep the result as a sequence,

val uniqueSubMatrices = subMatrices.distinct

And that's it. Full code just to illustrate:

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

It could be written as a single expression, but unless you break it up into functions, it's going to be horrible to read. And you'd either have to use the forward pipe (|>, not in the standard library), or add these functions implicitly to the types they act on, or it will be difficult to read anyway.

这篇关于从更大的矩阵中找到唯一的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！