Talk:Random Latin squares: Difference between revisions
Line 19: | Line 19: | ||
If you read the reference mentioned in the first sentence and think it is of use, then please add it to the task. |
If you read the reference mentioned in the first sentence and think it is of use, then please add it to the task. |
||
- --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 11:44, 9 June 2019 (UTC) |
- --[[User:Paddy3118|Paddy3118]] ([[User talk: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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 14:10, 9 June 2019 (UTC) |
Revision as of 14:10, 9 June 2019
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)