How can I structure for and if loops to construct Latin squares?

Question

My objective is to construct every unique Latin Square given a size n. The R command rlatin(n) uses a Markov chain to construct a random Latin Square of size n x n. However, this command won't just construct all Latin Squares of its size.

Below is my code:

library(magic)

L <- function(n){
  size <- factorial(n) * factorial(n-1)
  l <- list()
  l[[1]] <- rlatin(n)
  for(k in 2:size){
    new <- rlatin(n)
    for(j in 1:(k-1)){
      if(new == l[[j]]){
        new <- rlatin(n)
      }
    }
    l[[k]] <- new
  }
  l
}

This is not working properly, and I cannot see why. Can someone please shed some light on my errors? Additionally, once all Latin Squares are constructed, is there a way that I can organize them so there is some clear in the Latin Squares?

First, the question needs more clarity on the math of Latin Squares - Why would you try to find "every unique Latin Sq" that when it is known that even for a small n = 10, you would have about 9,982,437,658,213,039,871,725,064,756,920,320,000 unique solutions, and if you were to limit it to the reduced form, you would still have about 7,580,721,483,160,132,811,489,280 solutions. Source https://en.wikipedia.org/wiki/Latin_square). Your code does work for n=3 & if you have a newer computer with sufficient power, for n= 4 & 5. Hence, most likely a computational capability issue — aiatay7n, Mar 31 '20 at 01:44
Also, as clearly mentioned above the [r] tag, specify all non-base packages with `library()` calls. Where does `rlatin` function come from? — Edward, Mar 31 '20 at 01:47
Do you only want to construct the canonical form of the squares, or every permutation? If the latter, I'd suggest you generate all the permutations for each square you find, and only check the canonical form of any new square. Would be much more efficient. — Gregor Thomas, Mar 31 '20 at 02:16
@aiatay7n I really would only use this function to obtain every unique square for up to n=5. For some reason, this above code is not working for me when I use n=3. It obtains 12 latin squares, but some are duplicates. — Ron Snow, Mar 31 '20 at 17:05
@Edward It comes from the "magic" R package, which I cannot find a tag for. — Ron Snow, Mar 31 '20 at 17:07
@GregorThomas That sounds good. How would I go about doing that? — Ron Snow, Mar 31 '20 at 17:09
What part is giving you trouble? Put in canonical form - sort the columns (or rows) by first entry. Generating permutations? [Here's a FAQ](https://stackoverflow.com/q/11095992/903061), but `combinat::permn` is one good option. Permute `1:n` and reorder the columns for each of those. You don't even have to store any but the unique canonical order versions for each size. — Gregor Thomas, Apr 01 '20 at 13:51

Edward · Accepted Answer · 2020-03-31T18:23:53.187

1

Your code doesn't work to prevent duplicates because once your test of equality succeeds, you then find a new latin square, but then you don't test that new one with the current list of latin squares! You probably want a while loop, which breaks only when the current latin square is not identical to all previous ones. This can be assessed using sapply, although that maybe slow when n gets large.

L <- function(n) {
  size <- factorial(n) * factorial(n-1)
  l <- list()
  l[[1]] <- rlatin(n)
  for(k in 2:size) {
    new <- rlatin(n)
    while(sum(sapply(l, function(x) any(identical(x, new)))) > 0) {
      new <- rlatin(n)
    }
    l[[k]] <- new
  }
  l
}

For n=4 (size=144), the code takes only a few seconds. But for n=5 (size=2880), the code takes forever and a day. Perhaps there's a quicker solution.

L4 <- L(4)  # About 10 seconds.

Check for duplicates:

x <- list()
for(i in 1:length(L4)) {
    x[[i]] <- sapply(L4[-i], function(x) any(identical(x, L4[[i]])))
}

sum(sapply(x, sum))
# [1] 0

L5 <- L(5) # Still waiting... or as grampa used to say: 
                                            "you'll be wait'n til the cows come home".

Ah, finally.

   user  system elapsed 
 816.16    0.54  827.20

edited Mar 31 '20 at 18:23

answered Mar 31 '20 at 18:09

Edward

10,360
2
11
26

Your code looks great! Thank you so much. I do have several comments. This function quickly obtains L3 and L4; however, it does not appear able to compute L2. Additionally, L4 contains only 144 matrices, when Wikipedia says that there should be 576 unique Latin squares of order 4. – Ron Snow Mar 31 '20 at 22:07
L5 is a list of 2880 matrices, when it should be 161,280, too. I feel like we're really close, though! – Ron Snow Mar 31 '20 at 22:14
But your code initializes the list using `size`. That's your code, not mine. What should it be if not factorial (n) * factorial (n-1)? – Edward Mar 31 '20 at 23:44
I see. it should be n!*(n-1)!*(# of reduced Latin Squares) I fixed that part of my code, but for some reason, L2 does not work. Any ideas? – Ron Snow Apr 01 '20 at 00:02
1

That is due to `rlatin` function always returning the same latin square for n=2. Is that a bug? Seems trivial that there are only two possible. – Edward Apr 01 '20 at 00:37
1

Strangely, `rlatin(n=2, size=2)` gives both, but the result is in array form. – Edward Apr 01 '20 at 00:53
That's odd, well thanks for looking into that and all of your help. I appreciate it! :) – Ron Snow Apr 01 '20 at 01:03

How can I structure for and if loops to construct Latin squares?

1 Answers1