Talk:Random Latin squares: Difference between revisions
m
Thundergnat moved page Talk:Random Latin Squares to Talk:Random Latin squares: Follow normal task title capitalization policy
(→"restarting row" method: Further comment.) |
Thundergnat (talk | contribs) m (Thundergnat moved page Talk:Random Latin Squares to Talk:Random Latin squares: Follow normal task title capitalization policy) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 26:
===Non python algorithm===
Apart from selecting from almost none of the possible latin squares the 'python algorithm' has second disadvantage. Considering the above latin square if I move the rightmost column to in front of the leftmost, or the bottom row to above the top I produce the same result. That is there are varying number of ways of producing each of the small number of latin squares that this algorithm can produce. An alternative is to just permute the meaning of 0..4. This would produce a smaller subset of all possible latin squares, but almost none is almost none either way, and they would be uniform. This task was promoted from draft very quickly, I think it needs to go back to draft until this issue is resolved--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 09:30, 12 June 2019 (UTC)
:Or, you could state that a particular algorithm could generate any of all the possible Latin squares? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 11:13, 19 January 2020 (UTC)
=="restarting row" method==
To quote the factor solution:<br>
Line 186 ⟶ 189:
: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)
:Well found. The paper is so interesting I decided to give section 3.3 a go as a task see [[Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique]]--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 11:56, 5 August 2019 (UTC)
| |||