Talk:Random Latin squares

Python Algorithm

I got the mention of Latin squares from a stack-overflow question and a link to some solution methods that I did not read (and so did not add to the task as a reference).

I worked out that if you have a smaller solution of:

0 1
1 0

then the next larger solution (ignoring randomisation), could be got by: 1. Insert a copy of the first row at the end:

0 1
1 0
0 1

2. Insert the new symbol along the diagonal

2 0 1
1 2 0
0 1 2

I randomise the selection of symbol to insert at each recursive stage, and at the end swap rows randomly and swap columns randomly as these transformations preserve "Latin-ness".

If you read the reference mentioned in the first sentence and think it is of use, then please add it to the task.

- --Paddy3118 (talk) 11:44, 9 June 2019 (UTC)

"Randomness"

I don't actually use the algorithm in earnest, but several of the references mention the randomness of the generation.

I have no measure of the randomness, but thought that any number should be as likely to appear in any position in the square so I created a counter of how many times each symbol appeared in each cell of the square grid and present the counts for a million runs:

Additional Python: <lang python>def distributions(n, count):

   counters = [[defaultdict(int) for _ in range(n)] for __ in range(n)]
   range_n = range(n)
   for _ in range(count):
       square = rls(n)
       for r in range_n:
           for c in range_n:
               counters[r][c][ square[r][c] ] += 1
   for symbol in range_n:
       symcounts = [[counters[r][c][symbol] for c in range_n] for r in range_n]
       mx = max(cnt for row in symcounts for cnt in row)
       mn = min(cnt for row in symcounts for cnt in row)
       print(f'\n{symbol} distribution: from {mn} to {mx}\n==')
       print(_to_text(symcounts))

distributions(5, 1000_000)</lang>

Output:

0 distribution: from 199123 to 200657
==
199758 200268 199123 200194 200657
199878 200137 200165 199932 199888
200447 199564 200602 200024 199363
200094 200412 200266 199659 199569
199823 199619 199844 200191 200523

1 distribution: from 198960 to 200500
==
200057 200135 200085 199825 199898
200144 200249 199308 200118 200181
199297 200500 200268 200380 199555
200441 198960 200000 200317 200282
200061 200156 200339 199360 200084

2 distribution: from 198983 to 200849
==
200849 200156 200034 199978 198983
199747 199808 200144 200054 200247
199796 200405 199650 199895 200254
199820 199935 200178 199872 200195
199788 199696 199994 200201 200321

3 distribution: from 199433 to 200820
==
199816 199452 200527 200133 200072
200820 200003 199749 199598 199830
199769 199985 200143 199664 200439
199739 200558 199545 199932 200226
199856 200002 200036 200673 199433

4 distribution: from 199337 to 200691
==
199520 199989 200231 199870 200390
199411 199803 200634 200298 199854
200691 199546 199337 200037 200389
199906 200135 200011 200220 199728
200472 200527 199787 199575 199639

--Paddy3118 (talk) 14:10, 9 June 2019 (UTC)

Uniformity over all possible

I suspect this algorithm does not generate random latin squares uniformly. What matters is the uniformity of latin squares taken from the list of all latin squares. See https://math.stackexchange.com/questions/63131/generate-random-latin-squares . --Chunes (talk) 14:19, 9 June 2019 (UTC)

Hi Chunes, you're right!

I went back to the wikipedia article which has a table stating that the numbero f distinct n=4 LS is 576. This additional code: <lang python>In [97]: def distinct(n, count):

   ...:     distinct = Counter(tuple(rls(n)) for _ in range(count))
   ...:     print(f"Found {len(distinct)} different {n}-by-{n} Latin squares in {count} trials")
   ...: 
   ...: 

In [98]: distinct(4, 576_00) Found 432 different 4-by-4 Latin squares in 57600 trials

In [99]: </lang>

Shows that my algorithm cannot generate 25% of the possible outputs. It would have been nice if it could, but I won't disallow the algorithm as the task description isn't that precise.

Ideally I would find examples of what is missing and try and work out an additional algorithm that generates from the whole set. .... If time allowed.
--Paddy3118 (talk) 14:55, 9 June 2019 (UTC)

It might be worth mentioning that non-uniform solutions are acceptable in the task description. From my cursory research, it appears that generating a uniformly-random latin square is a difficult problem which either requires the exponential-time brute force approach of generating random permutations for rows and restarting the row if a clash occurs, or else requires implementing the involved Jacobson and Matthews algorithm. This also absolves us of some mathematical pedantry. :) --Chunes (talk) 15:14, 9 June 2019 (UTC)