LATIN_COVER
N Latin Squares which cover an NxN square.

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

Related Data and Programs:

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

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

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

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

• latin_cover.f, the source code.
• latin_cover.sh, BASH commands to compile the source code.

Examples and Tests:

• latin_cover_prb.f, a sample calling program.
• latin_cover_prb.sh, BASH commands to compile and run the sample program.
• latin_cover_prb_output.txt, the output file.

List of Routines:

• I4_MODP returns the nonnegative remainder of I4 division.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4BLOCK_PRINT prints an I4BLOCK.
• I4MAT_PRINT prints an I4MAT.
• I4MAT_PRINT_SOME prints some of an I4MAT.
• LATIN_COVER returns a 2D Latin Square Covering.
• LATIN_COVER_2D returns a 2D Latin Square Covering.
• LATIN_COVER_3D returns a 3D Latin Square Covering.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_PRINT prints a permutation.
• PERM_UNIFORM selects a random permutation of N objects.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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