Are there any previous studies about the general lexicographical orderings of Latin squares including random walks the space of all such orderings for a given order of Latin squares?
Are there any alternative (to backtracking) more efficient algorithms to deliver consecutive Latin squares on a general lexicographic order with consistent performance?
Background to this question.
I was seeking to determine how far in lexicographic order one needs to process to capture a representative of every isomorphic class of quasigroups of a given order. For order 5 the standard lexicographical order required a scan of the first 43667 quasigroups to identify a representative of each of the 1411 isomorphic classes. That is approx 27% of the total number of quasigroups i.e.161,280. I wondered what would be the effect of using other lexicographical orders – e.g. right to left, bottom to top rather than the standard left to right top to bottom over the cells of the square. Or, given the significance of diagonals why not give the main diagonal priority in defining a lexicographical order?
This led me to define a general lexicographic ordering of Latin squares as a sequence of coordinate pairs (row,column) defining, in order, the cells of the Latin square to be used in forming the key for the lexicographic order with each of the possible n^2 coordinate pairs occurring once and only once. Effectively this defines a sort key where every cell participates as a component of that key.
For example the standard definition for order 3 Latin squares is {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2), (3,3)}. Random lexicographic orderings are easily produced by shuffling (I use the GAP Shuffle function) such a definition.
As well as obtaining random lexicographic orders, one can also 'handcraft' them to obtain lexicographic orders with special properties. For example, any sequence starting {(1,1),(2,2),(3,3), …} defines a lexicographic order which prioritises the main diagonal and defines a lexicographic order where all the idempotent quasigroup tables are delivered consecutively at some point. A sequence which proceeds across the first row and then down the rest of the first column defines a lexicographic order which begins with all loops being delivered consecutively.
I found that processing along a general lexicographic order, from one Latin square to the next, could be implemented by a straightforward modification to a backtracking program developed previously for the standard order. Effectively the process moves backwards and forwards on the above definition to determine the coordinates of the next cell to be considered.
Incidentally, I found a lexicographic order which delivered a representative of each isomorphic class of order 5 quasigroups with a scan of about 10% of the total number.
My investigation (mostly empirical computer based) of these orderings have raised a number of interesting questions and I am looking for material which provides some theoretical underpinning to the results I have obtained.
The number of definitions of lexicographic orders for a given order n of Latin squares is (n^2)!. However the actual number of distinct lexicographical orders is significantly less than this as many different definitions can lead to the same lexicographic order. For example, while there are 9! = 362,880 definitions for order 3, there are only 288 distinct lexicographic orders. I have yet to determine the number of distinct lexicographic orders for order 4 Latin squares and anything higher appears to be a very computing power intensive. Is a theoretical approach available?
As a step toward understanding this I discovered that an actual lexicographic order is determined by the first part of the definition. For a given order of Latin square the number of elements of the definition required to ensure uniqueness requires further research. I also found that the number of corresponding pairs of Latin squares on two lexicographic orders which must be compared to determine equality was surprisingly high.
I then realised that the set of all lexicographic tracks (I use the word 'track' instead of 'order' from now on to avoid confusion with the order of the Latin squares involved), for Latin squares of a given order, forms a network upon which random walks could be performed. A walk is implemented by taking a number of steps from one Latin square to the next along a lexicographic track and then switching to another randomly generated track and repeating the process a number of times.
Clearly, any two Latin squares of a given order are connected by many different paths as every Latin square occurs on every track. Determination of the maximum shortest path between any two Latin squares would seem to be a challenging problem. Is it analysed anywhere?
Implementation appears to deliver uniformly distributed random Latin squares. Computer runs demonstrated this for order 3 and order 4 Latin squares and strongly indicated it is the case for order 5. I can see no reason why it should not be the case for higher orders.
The main problem is that performance of an untuned implementation on the full space of defined lexicographic orders deteriorates rapidly for Latin squares of order above about 9. This is because the backtracking implementation to move from one square to the next suffers from an extraordinarily high variability in the processing (number of iterations) needed to move from one Latin square to the next along on the general track. In fact the huge spikes in performance which occur intermittently along a track made me wonder if there were conditions under which the algorithm did not terminate. A proof that the backtracking algorithm always terminates needs further work.
This performance issue can be overcome to some extent by:
bailing out if a set number of iterations is exceeded and restarting at a previous Latin square or switching to another track;
limiting the set of track definitions from which a definition is is randomly chosen to a subset where this subset consists of 'higher performance' tracks.
This leads to my main subsidiary question: is there any radically different algorithm which does not involve backtracking which could deliver the next Latin square more efficiently? For example, could the bitrade between two consecutive Latin squares be computed (from the Latin square, its key and the track definition) and then applied to obtain the next square? Or could controlled (as distinct to random) moves of an incidence cube be directed toward forming the next Latin square on the track?
I found that a subset of track definitions formed by shuffling the rows or the columns of the standard definition have considerably better and more consistent performance. By also setting the number of switches and the bailout parameter appropriately, depending on the order of the Latin squares, it was possible to achieve acceptable performance for orders of Latin squares up to 30. This provided times approximately equal to the GAP/LOOPS Jacobson/Matthews implementation for orders up to 14 trending to 3 times the J/M implementation at order 25. Care needed to be taken in setting the parameters to ensure that tuning for performance did not affect the randomness of the result. Further research is required to determine optimum parameters and maybe identify other higher performing subsets of track definitions.
Interesting patterns and 'almost patterns' emerged when I graphed the sequences of number of iterations, depth of cells accessed and size of bitrade as processing moves from one Latin square to the next along a track.
A most interesting pattern was a mirror symmetry about the mid-point. I came across this when I was analysing the performance along a track. I was surprised to find that the second half of a lexicographical ordering mirrors the first half if each member of the first half is replaced by what I have called its “lexicographic complement”. If N is the total number of Latin squares of order n, then the Latin square in position N - k + 1 is equal to the 'lexicographical complement' of the one at position k. For example the first “smallest” and last “greatest” Latin squares are the complement of each other. This complement is defined as follows: in a situation where the set of symbols used in defining Latin squares is {0,1,2,...,n-1} the complement of a Latin square is formed by replacing each cell (i,j,v) with (i,j,n-v). I have not found any literature which mentions this concept of the complement of a Latin square and would be interested if a reference could be provided. I would be surprised if this simple mirror result is not well known as any enumeration of Latin squares in the 'standard order' would recognise that once half of the the Latin squares have been obtained the second half can be quickly computed using the complement.
There are interesting relationships between a Latin Square, the lexicographic key for that square on a track and the track definition:
every Latin square has a unique key associated with its position on a given track;
a properly constructed key does not necessarily (in fact not usually) determine a Latin square on a given track. The matrix formed by applying a key to a track definition does not often have the Latin square property;
a Latin square together with a properly constructed key can be realised on a large number ((n!)^n definitions) of tracks;
One of the implications of this is that every Latin square can appear as the first member in many lexicographic orderings. Take any Latin square and the lowest possible key for order n Latins squares. This key is {1,1,1,..,1,2,2,..2,....,n,n,..,n} where each symbol occurs n times. A large number of track definitions can be constructed where the Latin square has this key. Note: there are many tracks where the first member has a higher key than the above so in total there are many more lexicographic tracks where the given Latin square is the first member.
I was then fascinated by the idea that the above leads to an algorithm to deliver a random Latin square by calculating the first member of a randomly defined lexicographic order. Implementation showed the distribution is clearly uniform for order 3 Latin squares. More work is needed to determine the degree of uniformity for higher order Latin squares.
This algorithm also suffers from poor performance for Latin squares of order above 9 or 10 as it uses backtracking to deliver the first Latin square for a random track definition. I would be interested in any alternative algorithm.
It is clear that the above two approaches to generating random Latin squares cannot compete performance-wise with the Jacobson/Matthews algorithm for larger order Latin squares unless efficient alternatives to backtracking can be found.
