R: return largest consecutive pair of numbers in a matrix

Question

I am trying to write an R code to return the largest consecutive pair of numbers in a matrix. Consecutive pairs can be horizontal, vertical and both diagonals.

for example if i have matrix:

ma = array(c(8,4,3,1,7,5,9,15,6,10,16,11,2,14,12,13), dim = c(4,4))

the highest consecutive pairs for (1) horizontal: 16 and 12; (2) Vertical: 16 and 11 (3) diagonal (): 16 and 13; and (4) diagonal (/):16 and 15.

How can i do this in R?

Answer 1

Here is a solution using matrix arithmetic that will be much more efficient than a nested loop over the rows and columns, especially on large matrices.

directionalSums <- function(x){
  stopifnot(is.matrix(x))

  # padding functions to allow matrix addition
  padL  <- function(x) cbind(-Inf,x)
  padR  <- function(x) cbind(x,-Inf)
  padU  <- function(x) rbind(-Inf,x)
  padD  <- function(x) rbind(x,-Inf)

  # these padding functions are just for readability
  padLU <- function(x) padL(padU(x))
  padLD <- function(x) padL(padD(x))
  padRU <- function(x) padR(padU(x))
  padRD <- function(x) padR(padD(x))

  m <- nrow(x)
  n <- ncol(x)

  sumR <- padR( (padL(x) + padR(x))[1:m,2:n] )
  sumD  <- padD( (padU(x) + padD(x))[2:m,1:n])
  sumRD <- padRD( (padLU(x) + padRD(x))[2:m,2:n] )
  sumRU <- padRU( (padRU(x) + padLD(x))[2:m,2:n] )

  list(`right`=sumR, 
       `down`=sumD,
       `right and down`=sumRD,
       `right and up`=sumRU)

}

Let's try it out.

(sumList <- directionalSums(ma))

maxLocList <- lapply(sumList, function(x) which(x==max(x), arr.ind=TRUE))

for (i in 1:length(maxLocList) ){
  nameD <- names(maxLocList)[i]
  startCell <- maxLocList[[i]]
  maxSum <- sumList[[i]][startCell]
  x1 <- ma[startCell]
  x2 <- maxSum - x1
  writeLines(paste0('The max-sum consec. pair going ',
                    nameD, ' starts at [',
                    paste(startCell, collapse=', '),
                    '], with sum ', maxSum,
                    ' and components ', x1, ' and ',x2)
             )
}

Returns:

$right
     [,1] [,2] [,3] [,4]
[1,]   15   13    8 -Inf
[2,]    9   15   24 -Inf
[3,]   12   25   28 -Inf
[4,]   16   26   24 -Inf

$down
     [,1] [,2] [,3] [,4]
[1,]   12   12   16   16
[2,]    7   14   26   26
[3,]    4   24   27   25
[4,] -Inf -Inf -Inf -Inf

$`right and down`
     [,1] [,2] [,3] [,4]
[1,]   13   17   20 -Inf
[2,]   13   21   22 -Inf
[3,]   18   20   29 -Inf
[4,] -Inf -Inf -Inf -Inf

$`right and up`
     [,1] [,2] [,3] [,4]
[1,] -Inf -Inf -Inf -Inf
[2,]   11   11   12 -Inf
[3,]    8   19   30 -Inf
[4,]   10   31   23 -Inf

The max-sum consec. pair going right starts at [3, 3], with sum 28 and components 16 and 12
The max-sum consec. pair going down starts at [3, 3], with sum 27 and components 16 and 11
The max-sum consec. pair going right and down starts at [3, 3], with sum 29 and components 16 and 13
The max-sum consec. pair going right and up starts at [4, 2], with sum 31 and components 15 and 16

Answer 2

Here is a way to do it using simple (but long) code.

Since you're looking for the pair with the largest consecutive, you should firstly create a function which takes a cell and finds all of it's consecutive sums.

consec <- function(ma,y,x){
  return(
    c(if(x<ncol(ma))              ma[y,x] + ma[y,x+1],
      if(x>1)                     ma[y,x] + ma[y,x-1],
      if(y<nrow(ma))              ma[y,x] + ma[y+1,x],
      if(y>1)                     ma[y,x] + ma[y-1,x],
      if(x<ncol(ma) & y<nrow(ma)) ma[y,x] + ma[y+1,x+1],
      if(x>1 & y<nrow(ma))        ma[y,x] + ma[y+1,x-1],
      if(x<ncol(ma) & y>1)        ma[y,x] + ma[y-1,x+1],
      if(x>1 & y>1)               ma[y,x] + ma[y-1,x-1])
  )
}

The left half of this function (the if statements) make sure we don't go out of bounds, since a cell at the border will have less than 8 neighbors to form a consecutive pair with. The right half then get's the sum of the consecutive pair and adds it to the list.

Now, if you use consec(ma, 3, 2), it will give you a vector of the sums of the consecutives for ma[3,2].

Next, we want to fill up a second matrix with the highest consecutive sum for each cell. You can use the following code to create a blank matrix with the right dimensions.

ma2 <- matrix(0, nrow = nrow(ma), ncol = ncol(ma))

Now fill it using a loop and the consec function created earlier.

for(i in 1:nrow(ma)){
  for(j in 1:ncol(ma)){
    ma2[i,j] <- max(consec(ma,i,j)) 
  }
}

Now that we have our matrix of consecutive sums, we can find the largest sums in it, and the coordinates of it will correspond to where we want to look in the original matrix.

ma.max <- which(ma2 == max(ma2), arr.ind = TRUE)

Now, if there is only one pair of numbers which is the maximum, then ma.max will have two lines (the two permutations of the same pair). You can use:

ma[ma.max[1,1], ma.max[1,2]]; ma[ma.max[2,1], ma.max[2,2]]

To display them. In this case we get 15 and 16 so it worked.

If you have more maximums, then increase the numbers in the above code to get the next pair (3 and 4), and so on. You can even tweak the consec function, for example if you don't want diagonal consecutives then remove the last four lines of the list.