LATIN_COVER
N Latin Squares which cover an NxN square.

LATIN_COVER, a MATLAB 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
      

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 FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

latin_cover_test

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

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

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

• i4_modp.m, returns the nonnegative remainder of integer division;
• i4_uniform.m, returns a pseudorandom I4 in a given range;
• i4_wrap.m, forces an integer to lie between given limits;
• i4block_print.m, prints an I4BLOCK;
• i4mat_print.m, prints an I4MAT;
• i4mat_print_some.m, prints some of an I4MAT;
• latin_cover.m, returns a 2D Latin Square Covering.
• latin_cover_2d.m, returns a 2D Latin Square Covering.
• latin_cover_3d.m, returns a 3D Latin Square Covering.
• perm_check.m, checks that a permutation is legal.
• perm_mul.m, prints a permutation.
• perm_uniform.m, returns a random permutation.
• s_len_trim.m, returns the length of a string to the last nonblank.
• timestamp.m, returns the current YMDHMS date as a timestamp.