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: Nigel's conjecture is correct!) |
Thundergnat (talk | contribs) m (Thundergnat moved page Talk:Random Latin Squares to Talk:Random Latin squares: Follow normal task title capitalization policy) |
||
| (5 intermediate revisions by 4 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 46 ⟶ 49:
:::: My Go solution also uses the "restarting row" method which I certainly expected to be uniformly random but, when I ran Nigel's test, sure enough c and d occurred about twice as often as a and b. So it does demonstrate how easily one can be led astray by intuition in this sort of work. Anyway I'm going to rewrite the Go solution on the lines Nigel suggested earlier and will re-post later today. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 13:15, 17 July 2019 (UTC)
::::: Thanks for the correction, both of you. I wonder, did I misinterpret the algorithm as described in the paper, or is the author simply incorrect? Is the "restarting row" method actually more of a "restarting square" method? I will be looking to rewrite my submission as soon as I can wrap my head around an algorithm that works. --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 16:48, 17 July 2019 (UTC)
:::::: I've had a look at the paper and the author just seems to be wrong about the "restarting row" method producing uniformly random results. In fact the paper seems to be a bit self-contradictory. On the one hand it says in section 1.2:
:::::: "One thing that must be considered in SeqGen methods is that when a conflict is treated, correcting or replacing the repeated symbol can lead to a non-uniform distribution of the generated results."
:::::: On the other hand it says in section 2.1:
:::::: "Also, the generated results are uniformly distributed (if the PRNG used to generate the symbols in the row is not biased)."
:::::: But, as Nigel's example for a Latin square of order 4 clearly shows, what goes in the first two rows is inevitably affecting what goes in the third and fourth rows, not just in the order of the symbols but in the possible number of permutations of those rows and hence the probability distribution of the set of Latin squares being generated is not even approximately uniform. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 19:54, 17 July 2019 (UTC)
:: in particular, you may find this interesting: "The probability of finishing the entire LS is a combination of the previous series of probabilities, but not their product, as the rows are not independent to each other (i.e. row i depends of values on row i-1)." --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 19:37, 16 July 2019 (UTC)
Line 174 ⟶ 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)
| |||