[Math] Available lists of all latin squares up to order 5

combinatoricslatin-square

There are available online lists of the number of all latin squares up to order 11, e.g.: https://oeis.org/A002860. For a permutation-based test of a latin square design, one option is to fit the model to all of the latin squares of the same order to derive the sampling distribution of the test statistic. Rather than generate all the latin squares for a given size each time a permutation test is performed, I could just read in the set of latin squares from disk.

Given the difficulty in determining how many latin squares there are of order $n$, I presume that there aren't simple algorithms for generating all latin squares of order $n$ either. I was wondering, given that some researchers have actually gone to the trouble of computing the number of latin squares up to order 11, if lists of these latin squares were publicly available in electronic form somewhere?

If not, are there reliable algorithms for generating all latin squares for order $n$, $n \in {3, 4, 5}$?

(I have a simple R implementation that will give these for $n = 3$ but I started to struggle at $n = 4$).

Best Answer

The best source is Brendan McKay's website: http://users.cecs.anu.edu.au/~bdm/data/latin.html which contains the data up to order $8$ (for non-isotopic squares) or order $7$ (for all reduced squares).

For orders $n \geq 10$, there's simply too many (even if we exclude inequivalent ones).

For order $9$, researchers (such as Ian Wanless and his academic relatives) have been known to perform lengthy computations that iterate through main class representatives, usually using supercomputers or clusters of computers. This is not an easy task.

Related Solutions

Combinatorics – How to Generate Random Latin Squares

In the combinatorics community, the Jacobson and Matthews approach is widely considered the best approach to obtain random Latin squares (approximately) uniformly at random from the set of all Latin squares. A practical non-MCMC approach that samples uniformly would be extremely well-received (but seems beyond current techniques).

Other uniform sampling methods are:

Generating Latin squares row-by-row by appending random permutations and restarting whenever their is a clash gives the uniform distribution. [Or equivalently, uniformly sampling from the set of row-Latin squares, then restarting if there is a clash.]
Generating a list of all Latin squares, and picking one at random. Storage requirements could be reduced by (a) storing only a list of normalised Latin squares [i.e. first row in order] then randomly permuting the columns after sampling, and (b) storing only the differences between subsequent Latin squares (i.e. Latin trades) [although, this makes the algorithm more complicated].

In either case, for not particularly large n [maybe n>5], these approaches are either impractically slow, or requires impractically large storage space. However, for some applications, we don't need to sample $n \times n$ Latin squares for $n>5$, in which case, this is not a problem.

Moreover, for statistical applications, sampling from all possible Latin squares is often not necessary, in which case we just apply a random isotopism to any given Latin square (i.e. we pick a Latin square, then permute its rows, columns and symbols randomly).

Any attempt to sample via extending a Latin rectangle (or partial Latin square) to a Latin square without restarting from scratch after a clash occurs will almost certainly result in a non-uniform distribution. [I suppose theoretically you could add weights to your intermediate choices.] Different Latin rectangles admit a different number of completions, so if we don't restart from scratch, we will favour Latin squares that have Latin rectangles that admit fewer completions (i.e. there's less competition for those Latin squares).

This non-uniformity might seem like a subtle difference, but consider a $(n-2) \times n$ Latin rectangle. The number of completions is always a power of 2. If the number of completions is 1 (which can happen: take a cyclic group's Cayley table and delete the last two rows), then its completion is guaranteed to be generated from that point on. If the number of completions is $2^{n/2}$ (which can also happen: take the elementary abelian 2-group's Cayley table and delete the last two rows), then the probability of it being generated from that point on could be $2^{-n/2}$ (depending on how things are implemented). So, the difference in probabilities can be at least exponential in n.

Even if you don't care too much about the uniform distribution, the Jacobson and Matthews is still reasonable: it is quite fast and simple to implement (there's also implementations for GAP ("loops") and SAGE available, and probably others I'm unaware of).

Combinatorics – Algorithms for Mutually Orthogonal Latin Squares

The info given in the OP is almost correct. As noted in Jyrki Lahtonen's answer, $k$ cannot be congruent to $n$.

In $A_k(i,j)$, $k$ is the index of the square: the algorithm generates $n-1$ MOLS, one for each $k$ in $\{1,\cdots,n-1\}$. Using normal matrix conventions, $i$ is the row index and $j$ is the column index, but the formula still works if those are swapped.

Here's some rudimentary Python code that uses that formula to generate a set of mutually orthogonal Latin squares (MOLS) and then tests each combination for orthogonality. This code was originally developed using Python 2.6 but it runs correctly on Python 3.

In this code, $i$ and $j$ run from 0 to $n-1$ and $k$ runs from 1 to $n-1$; note that $n$ must be prime.

If you pass a composite value for $n$, the program will generate some Latin squares, and if that $n$ is odd you'll get some pairs of MOLS, which is useful if you want to construct magic squares.


""" Generate sets of mutually orthogonal Latin squares (MOLS)

    See https://math.stackexchange.com/a/1624875/207316

    Written by PM 2Ring 2016.01.24
    Updated 2021.01.31
"""

#from __future__ import print_function

import sys

def show_grid(g):
    for row in g:
        print(row)
    print()

def test_mols(g):
    """ Check that all entries in g are unique """
    a = set()
    for row in g:
        a.update(row)
    return len(a) == len(g) ** 2

def mols(n):
    """ Generate a set of mutually orthogonal Latin squares
        n must be prime
    """
    r = range(n)

    #Generate each Latin square
    allgrids = []
    for k in range(1, n):
        grid = []
        for i in r:
            row = []
            for j in r:
                a = (k*i + j) % n
                row.append(a)
            grid.append(row)

        # Test that there are no repeated items in the 1st column.
        # This test is unnecessary for prime n, but it lets us
        # produce some pairs of MOLS for odd composite n
        if len(set([row[0] for row in grid])) == n:
            allgrids.append(grid)

    for i, g in enumerate(allgrids):
        print(i)
        show_grid(g)

    print('- ' * 20 + '\n')

    # Combine the squares to show their orthogonality
    m = len(allgrids)
    for i in range(m):
        g0 = allgrids[i]
        for j in range(i+1, m):
            g1 = allgrids[j]
            newgrid = []
            for r0, r1 in zip(g0, g1):
                newgrid.append(list(zip(r0, r1)))
            print(i, j, test_mols(newgrid))
            show_grid(newgrid)

def main():
    # Get order from command line, or use default
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 5
    mols(n)

if __name__ == '__main__':
    main()

output for n=3


0
[0, 1, 2]
[1, 2, 0]
[2, 0, 1]

1
[0, 1, 2]
[2, 0, 1]
[1, 2, 0]

- - - - - - - - - - - - - - - - - - - - 

0 1 True
[(0, 0), (1, 1), (2, 2)]
[(1, 2), (2, 0), (0, 1)]
[(2, 1), (0, 2), (1, 0)]

output for n=5

0
[0, 1, 2, 3, 4]
[1, 2, 3, 4, 0]
[2, 3, 4, 0, 1]
[3, 4, 0, 1, 2]
[4, 0, 1, 2, 3]

1
[0, 1, 2, 3, 4]
[2, 3, 4, 0, 1]
[4, 0, 1, 2, 3]
[1, 2, 3, 4, 0]
[3, 4, 0, 1, 2]

2
[0, 1, 2, 3, 4]
[3, 4, 0, 1, 2]
[1, 2, 3, 4, 0]
[4, 0, 1, 2, 3]
[2, 3, 4, 0, 1]

3
[0, 1, 2, 3, 4]
[4, 0, 1, 2, 3]
[3, 4, 0, 1, 2]
[2, 3, 4, 0, 1]
[1, 2, 3, 4, 0]

- - - - - - - - - - - - - - - - - - - - 

0 1 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 2), (2, 3), (3, 4), (4, 0), (0, 1)]
[(2, 4), (3, 0), (4, 1), (0, 2), (1, 3)]
[(3, 1), (4, 2), (0, 3), (1, 4), (2, 0)]
[(4, 3), (0, 4), (1, 0), (2, 1), (3, 2)]

0 2 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 3), (2, 4), (3, 0), (4, 1), (0, 2)]
[(2, 1), (3, 2), (4, 3), (0, 4), (1, 0)]
[(3, 4), (4, 0), (0, 1), (1, 2), (2, 3)]
[(4, 2), (0, 3), (1, 4), (2, 0), (3, 1)]

0 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 4), (2, 0), (3, 1), (4, 2), (0, 3)]
[(2, 3), (3, 4), (4, 0), (0, 1), (1, 2)]
[(3, 2), (4, 3), (0, 4), (1, 0), (2, 1)]
[(4, 1), (0, 2), (1, 3), (2, 4), (3, 0)]

1 2 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(2, 3), (3, 4), (4, 0), (0, 1), (1, 2)]
[(4, 1), (0, 2), (1, 3), (2, 4), (3, 0)]
[(1, 4), (2, 0), (3, 1), (4, 2), (0, 3)]
[(3, 2), (4, 3), (0, 4), (1, 0), (2, 1)]

1 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(2, 4), (3, 0), (4, 1), (0, 2), (1, 3)]
[(4, 3), (0, 4), (1, 0), (2, 1), (3, 2)]
[(1, 2), (2, 3), (3, 4), (4, 0), (0, 1)]
[(3, 1), (4, 2), (0, 3), (1, 4), (2, 0)]

2 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(3, 4), (4, 0), (0, 1), (1, 2), (2, 3)]
[(1, 3), (2, 4), (3, 0), (4, 1), (0, 2)]
[(4, 2), (0, 3), (1, 4), (2, 0), (3, 1)]
[(2, 1), (3, 2), (4, 3), (0, 4), (1, 0)]