CODEWITHSUNDEEP
kotlinmatrixmultidimensional-arraywindowed
Alexander Ites
Alexander Ites

Reputation: 510

How to collect m size 2D arrays/lists (sub matrices) of n 2D array/list (matrix) where m < n in Kotlin functionally?

I want to find overlapping 2D list/arrays (sub matrices) of a 2D list/array (matrix) looking like:

[
  [ 1, 2, 3, 4 ],
  [ 5, 6, 7, 8 ],
  [ 9, 1, 2, 3 ]
]

In simple case I need to get all overlapping squares of size m, that is m x m size overlapping 2D list/arrays. For example, in the case above let m be 3.

In imperative way I do the following:

for (i in 0 until matrix.size - m) {
  for (j in 0 until matrix.size - m) {
    var q = mutableListOf<Int>()       // can be a real 2D list, here a plain list to simplify
    for (k in i..i + m) {
      for (l in j..j + m) {
        q.add(matrix[m][n])
      }
    }
    // add an m size matrix to result here
  }
}

I have tried some stuff with windowed(m) and mapping ranges using m as upper bound inside but can't come up with a working solution.

Please share if you know how to make it in Kotlin in functional way. One-liner is not a must yet would be great.

Upvotes: 0

Views: 70

Answers (2)

tyg
tyg

Reputation: 16202

You can use this:

fun Iterable<Iterable<Int>>.subMatrices(size: Int): List<List<List<Int>>> =
    windowed(size) { window ->
        window.map {
            it.windowed(size)
        }.fold(emptyList<List<List<Int>>>()) { acc, it ->
            if (acc.isEmpty())
                it.map(::listOf)
            else
                acc.zip(it) { a, b -> a.plus(element = b) }
        }
    }.flatten()

You only specify n and m in the example, where n = 5 and m = 3. Your initial matrix is of size 3/5, but the 3 does seem to be only coincidently the same as m. To handle a matrix with more rows the first windowed is necessary to create m-sized chunks.

The second windowed is probably what you had in mind, it slides over the columns. What you were missing is the subsequent fold. It allows you to properly merge the windowed rows.

With this, calling

listOf(
    listOf(1, 2, 3, 4),
    listOf(5, 6, 7, 8),
    listOf(9, 1, 2, 3),
).subMatrices(3)

produces

[
    [
        [1, 2, 3],
        [5, 6, 7],
        [9, 1, 2],
    ],
    [
        [2, 3, 4],
        [6, 7, 8],
        [1, 2, 3],
    ],
]

Edit:

Depending on how large your matrices are, performance may be an issue. In that case you could make the accumulator for the fold operation mutable, so adding to a list doesn't create new lists with the previous ones thrown away:

fun Iterable<Collection<Int>>.subMatrices(size: Int): List<List<List<Int>>> =
    windowed(size) { window ->
        window.map {
            it.windowed(size)
        }.fold(List(maxOf { it.size }) { mutableListOf<List<Int>>() }) { acc, it ->
            acc.zip(it) { a, b -> a.apply { add(b) } }
        }
    }.flatten()

Upvotes: 1

Ram&#243;n Castillo
Ram&#243;n Castillo

Reputation: 1

If I undertood, in the example your output should be

    [[1, 2, 3], 
     [5, 6, 7], 
     [9, 1, 2]]

    [[2, 3, 4], 
     [6, 7, 8], 
     [1, 2, 3]]

so

matrix_width = matrix.get(0).size
matrix_height = matrix.size
new_matrix = mutableListOf<MutableList<Int>>()
shift_width = matrix_width - m
shift_height = matrix_height - m
for(width in 0 until shift_width){
    for(height in 0 until shift_height){
        for(i in width until m+width){
            for(j in height until m+height){
                new_matrix[i][j] = matrix[i][j]
            }
        }
    }
}

did not try if it works but i think that's the logic

Upvotes: -1

Related Questions