从更大的矩阵中找到唯一的矩阵

发布于 2024-10-16 01:25:08 字数 1244 浏览 7 评论 0原文

我对函数式编程相当陌生，所以我正在进行一些练习。我想编写一个函数，给定一个唯一自然数矩阵（假设为 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，但似乎无法弄清楚。它出来了。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

甚是思念 2024-10-23 01:25:08

你已经成功一半了。事实上，我很难弄清楚如何做你已经做过的事情。我对你的代码进行了一些分解，以便更容易理解。另外，我将 array2D 设为 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

它可以写成单个表达式，但除非将其分解为函数，否则读起来会很糟糕。您要么必须使用前向管道（|>，不在标准库中），要么将这些函数隐式添加到它们所作用的类型中，否则无论如何都难以阅读。

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

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.

回复收藏 0 原文

你另情深 2024-10-23 01:25:08

编辑：好吧，我想我终于明白你想要什么了。我将展示一种有效的方法，而不是高性能的方法。（这通常是类似于 Java 的可变解决方案，但您已经知道如何做到这一点。）

首先，您真的、真的应该使用您自己的、在 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

您编写了一个并排矩阵的结构，您也可以付出一些努力来做到这一点（同样，因为从 1D 操作创建 2D 操作并不总是那么简单）：（

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

注意，reduceRight 到使其成为 O(n) 操作而不是 O(n^2)——连接到长累积列表的末尾是一个坏主意——但还要注意，矩阵太多，这可能会溢出堆栈）。

Edit: Okay, I think I finally understand what you want. I'm going to show a way that works, not a way that is high-performance. (That's generally the mutable Java-like solution, but you already know how to do that.)

First, you really, really ought to do this with your own collections that work in 2D sensibly. Using a bunch of 1D collections to emulate 2D collections is going to lead to unnecessary confusion and complication. Don't do it. Really. It's a bad idea.

But, okay, let's do it anyway.

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

This is the whole matrix that you want. Next,

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

are the groups of rows that you want. Now, you should have been using a 2D data structure, because you want to do something that doesn't map well onto 1D operations. But:

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

If you carefully pull this apart, you see that you're creating a bunch of iterators (xss.map(_.sliding(3))) and then iterating through them all in lock step by keeping hold of those same iterators step after step, stopping when at least one of them is empty, and mapping them onto their next values (which is how you walk forward with them).

Now that you've got the matrices you can store them however you want. Personally, I'd flatten the list:

val flattened = small.flatten

You wrote a structure that has the matrices side by side, which you can also do with some effort (again, because creating 2D operations out of 1D operations is not always straightforward):

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

(note reduceRight to make this an O(n) operation instead of O(n^2)--joining to the end of long accumulating lists is a bad idea--but note also that with too many matrices this will probably overflow the stack).

回复收藏 0 原文

~没有更多了~