Uniform Generation of Random Latin Rectangles

Abstract

We show how to generate $k\times n$ Latin rectangles uniformly at random in expected time $O(n{k}^3)$, provided $k=o(n^{1/3})$. The algorithm uses a switching process similar to that recently used by us to uniformly generate random graphs with given degree sequences.