find unique matrices from a larger matrix

Question

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.

Answer 1

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.

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