Clever Geek Handbook

Sorting matrix rows according to the number of different digits

I have a matrix containing strings 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 is only 1 digit away from its direct neighbors (above and below).

Can this be done?

+3


source to share


2 answers


Interest Ask! The way I decided to do it is to recursively construct such a matrix of ones with fewer digits. Suppose we have an n-bit matrix (containing all 2 ^ n unique n-bit sequences), where each neighbor differs by at most one. If we use rbind

this matrix with its inversion (row by row), then each row of the result will differ by no more than 1, and the two rows on the right in the middle will be the same. We can add 0 in front of the first half and 1 in front of the second half. The result contains all 2 ^ (n + 1) unique (n + 1) -bit sequences, and all neighbors have a distance of at most 1 from each other.

For the base case, we can use (0 1) for a 1-valued 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 constructing these matrices is that the first and last rows will also have a distance of 1 from each other.

+5


source


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

# 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 is if you treated strings as decimal integers:

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

enter image description here



There is obviously a pattern. It looks "non-stationary", so I made the first differences:

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

enter image description here

After checking this graph by several n, the algorithm jumps out higher. 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
+2


source






More articles:


All Articles