latin_cover


latin_cover, a FORTRAN90 code which produces a set of N Latin Squares which cover an NxN square.

Given an NxN grid, a Latin Square is a selection of N pairs of indices (I,J) such that every possible value of I and J occurs exactly once. A picture for the case N = 5 may suggest what is going on:

          - - - 1 -
          - 1 - - -
        I 1 - - - -
          - - - - 1
          - - 1 - -
              J
      
The above Latin Square can also be described by the index pairs (1,4), (2,2), (3,1), (4,5), (5,3).

A Latin square will always contain N index pairs. Since the original square contains NxN index pairs, it is interesting to speculate whether it would be possible to find N Latin squares with the property that every possible index pair (I,J) in the NxN square occurs in exactly one of the Latin Squares. In that case, we would say that the Latin Squares "cover" or decompose the square.

Here is an example which starts with the Latin square pictured above, and generates 4 more Latin squares to cover the 5x5 square.

          3 2 5 1 4
          2 1 4 5 3
        I 1 5 3 4 2
          5 4 2 3 1
          4 3 1 2 5
              J
      

Given a value N, this program produces a Latin cover for an NxN square.

Given a description of a Latin square of order N, this program produces N-1 more Latin squares, so that together with the input Latin square, a Latin cover is produced.

It is also possible to generate a 3D Latin covering. Here, a single Latin cube contains only N subcubes, so we require NxN such cubes if we have a hope of covering all the subcubes. The routine LATIN_COVER_3D will compute such a covering.

A small example of a 3D a Latin Cover:

 
       K =        1
 
        J:       1       2       3
       I:
       1:        4       1       7
       2:        6       3       9
       3:        5       2       8
 
       K =        2
 
        J:       1       2       3
       I:
       1:        3       9       6
       2:        2       8       5
       3:        1       7       4
 
       K =        3
 
        J:       1       2       3
       I:
       1:        8       5       2
       2:        7       4       1
       3:        9       6       3
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

latin_cover is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version.

Related Data and Programs:

latin_cover_test

latinize, a FORTRAN90 code which adjusts N points in M dimensions to form a Latin hypercube.

Reference:

  1. Herbert Ryser,
    Combinatorial Mathematics,
    Mathematical Association of America, 1963.

Source Code:


Last revised on 24 July 2020.