CODEWITHSUNDEEP
rmatrix
upabove
upabove

Reputation: 1119

Sort rows of matrix according to number of different digits

I have a matrix that contains rows of binary vectors:

library(gtools)
mat<-permutations(2,6,v=c(0,1),repeats.allowed=TRUE)

I would like to sort the rows of the matrix so that each row differs by only 1 digit from its direct neighbours (above and below).

Is this possible to do?

Upvotes: 3

Views: 116

Answers (2)

Matthew Plourde
Matthew Plourde

Reputation: 44614

Here's another recursive approach, thanks for the idea @josilber. 

# calculates the decimal difference between adjacent (1 digit difference) 
# binary digits of length n, starting with 2.
diffs <- function(n) {
    if (n == 1) {
        return(n)
    } else {
        k <- Recall(n - 1)
        c(k, 2^(n-1), rev(-k))
    }
}

get.mat2 <- function(ncols) {
    adj.ints <- rev(cumsum(c(0, diffs(ncols)))) # get all differences
    mat32 <- matrix(rev(as.integer(intToBits(adj.ints))), ncol=32, byrow=TRUE) # convert to binary representation in matrix
    mat32[, (33-ncols):32] # remove extraneous columns
}

I was curious what the pattern was if you viewed the rows as decimal integers:

m <- get.mat(8)
ints <- strtoi(apply(m, 1, paste, collapse=''), 2)
plot(ints, type='b')

enter image description here

There's obviously a pattern. It looks "non-stationary", so I took the first differences:

diffs <- diff(strtoi(apply(m, 1, paste, collapse=''), 2))
plot(diffs, type='b')

enter image description here

After inspecting this graph for a few n, the algorithm above jumps out. As a secondary note, this method doesn't seem to be significantly faster:

ncols <- 20
system.time(josilber <- get.mat(ncols))
#   user  system elapsed 
#   1.90    0.13    2.05 
system.time(plourde <- get.mat2(ncols))
#   user  system elapsed 
#   1.61    0.19    1.81 
josilber <- matrix(as.integer(josilber), ncol=ncol(josilber))
identical(josilber, plourde)
# TRUE

Upvotes: 2

josliber
josliber

Reputation: 44330

Interesting question! A way I thought of to accomplish this is to recursively build such a matrix from ones with a smaller number of digits. Let's assume we have a n-digit matrix (containing all the 2^n unique n-bit sequences) where each neighbor differs at most by one. If we rbind this matrix with its reversal (by rows), then each row of the result will differ by at most 1, and the two rows right in the middle will be identical. We can add a 0 in front of the first half and a 1 in front of the second half. The result contains all 2^(n+1) unique (n+1)-bit sequences, and all neighbors have distance at most 1 from each other.

For a base case, we can use (0 1) for the 1-digit matrix.

get.mat <- function(size) {
  if (size == 1) {
    return(matrix(c(0, 1), ncol=1))
  } else {
    smaller <- get.mat(size-1)
    return(rbind(cbind(0, smaller), cbind(1, smaller[nrow(smaller):1,])))
  }
}
get.mat(4)
#  [1,]    0    0    0    0
#  [2,]    0    0    0    1
#  [3,]    0    0    1    1
#  [4,]    0    0    1    0
#  [5,]    0    1    1    0
#  [6,]    0    1    1    1
#  [7,]    0    1    0    1
#  [8,]    0    1    0    0
#  [9,]    1    1    0    0
# [10,]    1    1    0    1
# [11,]    1    1    1    1
# [12,]    1    1    1    0
# [13,]    1    0    1    0
# [14,]    1    0    1    1
# [15,]    1    0    0    1
# [16,]    1    0    0    0

An interesting side effect of the approach for building these matrices is that the first and last rows will also have distance 1 from each other.

Upvotes: 5

Related Questions