Generation of random latin squares step by step and graphically
In order to generate random Latin squares of order 256, the Jacobson and Matthews’ algorithm has been implemented in Java. Clear and efficient data structures (for squares and incidence cubes) have been modeled and the ±1-moves of their method have been implemented. This ensures that, in a polynomia...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/42155 |
| Aporte de: |
| Sumario: | In order to generate random Latin squares of order 256, the Jacobson and Matthews’ algorithm has been implemented in Java. Clear and efficient data structures (for squares and incidence cubes) have been modeled and the ±1-moves of their method have been implemented. This ensures that, in a polynomial number of steps (O(<i>n</i>3)), the algorithm finishes with a Latin square as a result that is approximately uniformly distributed.
As an additional contribution to the subject, a step-by-step graphical generation using OpenGL (Open Graphic Library) is provided, which could be used to explain the algorithm, understand it or simply draw the resulting Latin squares as incidence cubes.
The main goal of the present work is to document the implementation of the algorithm and make it public on the Internet, since no standard implementation is freely available. |
|---|