Create matrix with entries unique to row and column R

Question

I need to find all possible 5x5 matrix of integers 1-5 unique to each row and column (imagine a Sudoku) in R.

Is there any efficient way of doing this without creating all 120C5 matrices and then finding the fitting ones?

Thank you!

Answer 1

As I said in my comment above, matrices of this type are called Latin squares.

For a start, we already know that there are 56 so-called reduced Latin squares and 161280 all Latin squares of size 5. The reduced Latin squares are such that both the first column and the first row are just 1, 2, 3, 4, 5 (in this order). Given those reduced Latin squares, one may easily (as long as the size is not greater than 5) generate all Latin squares: permute all the rows except the first one and permute all the columns. Hence, as expected, 161280=5!*4!*56.

By restricting the first row and column one could generate 4!*3!*2!=288 matrices and check which 56 are Latin squares. However, I'm going to skip that and take their list from here.

First we read and rearrange the data

reduced <- read.table("http://users.cecs.anu.edu.au/~bdm/data/reduced5.txt", head = FALSE, colClasses = "character")
reduced <- lapply(1:nrow(reduced), function(r) matrix(as.numeric(unlist(strsplit(unlist(reduced[r, ]), ""))) + 1, 5))
length(reduced)
# [1] 56

Now let's generate all 5! and 4! permutations of 1, 2, 3, 4, 5 and 1, 2, 3, 4, respectively.

library(combinat)
perms5 <- permn(1:5)
perms4 <- permn(1:4)

Lastly, we go over all the reduced Latin squares and permute them in all possible ways

allLS <- sapply(reduced, function(m) {
  LS <- vector("list", gamma(6) * gamma(5))
  for(i in 1:gamma(5))
    for(j in 1:gamma(6))
      LS[[(i - 1) * gamma(6) + j]] <- m[perms4[[i]] + 1, perms5[[j]]]
  LS
})

Takes just a couple of seconds and we have the result

length(allLS)
# [1] 161280

It is easy to verify that they all are different

table(table(sapply(allLS, paste0, collapse = "")))
#      1 
# 161280 

and you could also check if they all are Latin squares.