LATIN_COVER
N Latin Squares which cover an NxN square.


LATIN_COVER is a C library 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 GNU LGPL license.

Languages:

LATIN_COVER is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LATIN_CENTER, a C++ library which computes elements of a Latin Hypercube dataset, choosing center points.

LATIN_EDGE, a C++ library which computes elements of a Latin Hypercube dataset, choosing edge points.

LATIN_RANDOM, a C++ library which computes elements of a Latin Hypercube dataset, choosing points at random.

LATINIZE, a C library 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:

Examples and Tests:

List of Routines:

You can go up one level to the C source codes.


Last revised on 05 August 2012.