The random generation of Latin rectangles based on the assignment problem
Fariha Iftikhar, Gábor P. Nagy · Discrete Applied Mathematics · 2025
We investigate the random generation of Latin rectangles using a method based on the assignment problem. Specifically, each row is selected via a minimum-cost permutation from a randomly generated cost matrix. This approach defines a convex polytope for each Latin rectangle, where the volume of the polytope determines the sampling probability of the corresponding rectangle. Our analysis reveals that the resulting process is efficient but generally non-uniform, thereby providing a negative answer to a question posed by the second author in 2009. Furthermore, we establish that the volume of the polytope is invariant under column and symbol permutations of the rectangles.