Talk:Random Latin squares: Difference between revisions
Ruthless hillclimbing method
(→"restarting row" method: Further comment.) |
(Ruthless hillclimbing method) |
||
Line 186:
:Thanks. Changed. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 14:33, 12 June 2019 (UTC)
:: Well ... That still makes no sense at all ... How can a Latin square "generate" the values which constitute it ? Perhaps what the incoherence (and attempted circularity) of that sentence expresses is really a need for a slightly more solid concept of what is actually being asked for here ? [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:34, 12 June 2019 (UTC)
==Ruthless Hillclimbing Method==
To quote a method for generating uniformly random latin squares from page 20 of https://pdfs.semanticscholar.org/4a7c/d245f6f6a4ef933c6cf697832607f71a39c1.pdf,
"Another, more ruthless method, is a modification of hill climbing. This time, do not worry about finding SDRs, merely look at all possible permutations and select one uniformly at random to add as the next row. If, in doing so, you violate the rules of being a Latin square, restart the entire process. This method terminates with probability 1 and does achieve the uniform distribution. However, if L(n) is the total number of LS(n), the expected number of restarts is n!(n−1/L(n)) =e^(n^2(1+o(1))); an unacceptable price to pay for uniformity [29]."
I have implemented this algorithm and in my testing, it does not suffer from the specific lack of uniformity described by Nigel above. (Squares A, B, C, and D are generated with the same frequency.) I am hopeful that this is a method for generating uniformly random latin squares. Although inefficient, it suffices for generating squares of order 5. --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 15:59, 18 July 2019 (UTC)
| |||