Combinatorics – Algorithms for Mutually Orthogonal Latin Squares

algorithmscombinatoricslatin-square

I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a foreign language, I did find a formula including the source code.

This is said to be a formula to construct a series of squares (if $n$ is a prime number):

For $k, i, j \in \{1,2, \cdots, n\}$
$$A_k(i, j) = [k \cdot (i-1) + (j-1)] \mod n$$

Is this correct? I tried to find other sources but failed.

If this is correct, what is meant by $k$, $i$ and $j$? In the code, they pass "size" of the latin square to all of these variables.

Best Answer

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)]
Related Question