Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions
Content added Content deleted
(Realize in F#) |
Thundergnat (talk | contribs) (Thundergnat moved page Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique to Latin Squares in reduced form/Randomizing using Jacobson and Matthews' technique: captialization policy) |
||
| (20 intermediate revisions by 8 users not shown) | |||
| Line 1: | Line 1: | ||
#REDIRECT [[Latin Squares in reduced form/Randomizing using Jacobson and Matthews' technique]] |
|||
{{draft task}} |
|||
Section 3.3 of [[https://pdfs.semanticscholar.org/4a7c/d245f6f6a4ef933c6cf697832607f71a39c1.pdf Generalised 2-designs with Block Size 3(Andy L. Drizen)]] describes a method of generating Latin Squares of order n attributed to Jacobson and Matthews. The purpose of this task is to produce a function which given a valid Latin Square transforms it to another using this method. |
|||
;part 1 |
|||
Use one of the 4 [[Latin Squares in reduced form]] of order 4 as X0 to generate 10000 Latin Squares using X(n-1) to generate X(n). Convert the resulting Latin Squares to their reduced form, display them and the number of times each is produced. |
|||
;part 2 |
|||
As above for order 5, but do not display the squares. Generate the 56 [[Latin Squares in reduced form]] of order 5, confirm that all 56 are produced by the Jacobson and Matthews technique and display the number of each produced. |
|||
;part 3 |
|||
Generate 750 Latin Squares of order 42 and display the 750th. |
|||
;part 4 |
|||
Generate 1000 Latin Squares of order 256. Don't display anything but confirm the approximate time taken and anything else you may find interesting |
|||
=={{header|F_Sharp|F#}}== |
|||
===The Functions=== |
|||
<lang fsharp> |
|||
// Jacobson and Matthews technique for generating Latin Squares. Nigel Galloway: August 5th., 2019 |
|||
let R=let N=System.Random() in (fun n->N.Next(n)) |
|||
let jmLS α X0= |
|||
let X0=Array2D.copy X0 |
|||
let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2]) |
|||
let rec randLS i j z i' j' z'= |
|||
X0.[i,j']<-z'; X0.[i',j]<-z' |
|||
match X0.[i',j']=z' with |
|||
true->X0.[i',j']<-z; X0 |
|||
|false->randLS i' j' z' (List.find(fun n->X0.[n,j']=z')(N())) (List.find(fun n->X0.[i',n]=z')(N())) (if (R 2)=0 then let t=X0.[i',j'] in X0.[i',j']<-z; t else z) |
|||
let i,j=R α,R α |
|||
let z =let z=1+(R (α-1)) in if z<X0.[i,j] then z else 1+(z+1)%α |
|||
let i',j',z'=let N=[0..α-1] in (List.find(fun n->X0.[n,j]=z) N,List.find(fun n->X0.[i,n]=z) N,X0.[i,j]) |
|||
X0.[i,j]<-z; randLS i j z i' j' z' |
|||
let asNormLS α= |
|||
let n=Array.init (Array2D.length1 α) (fun n->(α.[n,0]-1,n))|>Map.ofArray |
|||
let t=Array2D.init (Array2D.length1 α) (Array2D.length1 α) (fun i j->α.[n.[i],j]) |
|||
let g=Array.init (Array2D.length1 α) (fun n->(t.[0,n]-1,n))|>Map.ofArray |
|||
Array2D.init (Array2D.length1 α) (Array2D.length1 α) (fun i j->t.[i,g.[j]]) |
|||
let randLS α=Seq.unfold(fun g->Some(g,jmLS α g))(Array2D.init α α (fun n g->1+(n+g)%α)) |
|||
</lang> |
|||
===The Task=== |
|||
;part 1 |
|||
<lang fsharp> |
|||
randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iter(fun n->printf "%A was produced %d times\n\n" (fst n)(snd n)) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
[[1; 2; 3; 4] |
|||
[2; 3; 4; 1] |
|||
[3; 4; 1; 2] |
|||
[4; 1; 2; 3]] was produced 2920 times |
|||
[[1; 2; 3; 4] |
|||
[2; 4; 1; 3] |
|||
[3; 1; 4; 2] |
|||
[4; 3; 2; 1]] was produced 2262 times |
|||
[[1; 2; 3; 4] |
|||
[2; 1; 4; 3] |
|||
[3; 4; 2; 1] |
|||
[4; 3; 1; 2]] was produced 2236 times |
|||
[[1; 2; 3; 4] |
|||
[2; 1; 4; 3] |
|||
[3; 4; 1; 2] |
|||
[4; 3; 2; 1]] was produced 2582 times |
|||
</pre> |
|||
;part 2 |
|||
<lang fsharp> |
|||
randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iteri(fun n g->printf "%d(%d) " (n+1) (snd g)); printfn "" |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
1(176) 2(171) 3(174) 4(165) 5(168) 6(182) 7(138) 8(205) 9(165) 10(174) 11(157) 12(187) 13(181) 14(211) 15(184) 16(190) 17(190) 18(192) 19(146) 20(200) 21(162) 22(153) 23(193) 24(156) 25(148) 26(188) 27(186) 28(198) 29(178) 30(217) 31(185) 32(172) 33(223) 34(147) 35(203) 36(167) 37(188) 38(152) 39(165) 40(187) 41(160) 42(199) 43(140) 44(202) 45(186) 46(182) 47(175) 48(161) 49(179) 50(175) 51(201) 52(195) 53(205) 54(183) 55(155) 56(178) |
|||
</pre> |
|||
;part 3 |
|||
<lang fsharp> |
|||
let q=Seq.item 749 (randLS 42) |
|||
for n in [0..41] do (for g in [0..41] do printf "%3d" q.[n,g]); printfn "" |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
16 7 41 15 17 40 12 9 10 5 19 29 21 18 8 22 3 36 23 31 11 38 13 30 2 33 6 42 39 14 32 20 28 35 26 1 34 37 27 24 4 25 |
|||
38 25 36 32 40 29 35 27 8 26 31 15 9 7 16 11 4 3 12 20 23 33 5 24 41 14 30 34 42 17 39 18 37 22 21 13 1 10 6 19 2 28 |
|||
8 34 27 25 21 31 1 23 37 36 26 13 22 24 35 17 10 40 41 30 42 7 15 2 18 3 29 11 32 4 38 39 9 5 16 14 28 12 20 33 19 6 |
|||
33 35 13 34 15 24 4 29 41 27 3 17 10 26 39 23 30 32 1 38 16 25 37 14 6 28 19 9 40 5 18 7 42 11 31 20 12 22 2 21 8 36 |
|||
2 42 20 1 7 26 11 10 39 41 34 22 40 23 24 29 14 17 5 33 38 30 6 13 3 16 18 19 31 15 28 21 36 37 32 27 8 4 25 9 35 12 |
|||
25 33 14 40 28 30 31 24 29 4 8 20 26 38 12 35 2 39 16 6 13 21 18 17 5 41 23 3 36 7 34 22 27 1 10 42 11 19 15 32 37 9 |
|||
17 22 35 28 30 18 21 2 15 39 5 40 27 13 1 34 38 37 26 23 41 36 4 3 11 6 20 8 9 10 12 24 31 25 7 29 16 32 42 14 33 19 |
|||
14 9 19 7 26 15 10 4 36 25 22 23 39 16 2 40 18 1 38 13 21 37 34 31 35 24 12 27 11 3 5 6 17 20 41 33 32 29 8 30 28 42 |
|||
5 27 24 13 2 36 25 30 23 9 6 14 35 15 42 39 16 26 21 34 33 31 3 1 29 12 38 17 37 19 40 4 7 8 22 41 20 28 32 10 18 11 |
|||
19 41 28 26 8 10 30 35 18 33 15 27 25 21 29 42 23 12 17 2 5 1 38 6 20 7 34 4 13 36 24 31 14 3 11 32 39 40 9 22 16 37 |
|||
41 10 3 19 22 9 27 40 1 29 16 42 33 39 34 7 37 20 11 12 4 18 35 8 28 26 36 5 17 30 25 32 6 15 24 21 13 23 14 2 38 31 |
|||
42 3 16 36 33 21 20 14 31 22 9 38 29 19 37 13 28 10 35 18 39 26 25 27 4 30 15 23 41 24 11 1 40 7 5 17 6 2 12 8 34 32 |
|||
23 31 34 41 38 33 3 28 4 1 30 25 6 2 20 14 13 24 8 42 7 12 39 32 22 29 5 37 15 9 27 10 35 36 19 40 17 18 16 11 26 21 |
|||
37 16 30 11 4 32 42 33 13 6 14 2 15 27 18 31 20 41 39 40 9 24 36 5 10 8 1 26 3 34 22 28 38 19 29 23 21 25 35 12 17 7 |
|||
1 19 26 22 16 25 36 39 3 23 41 37 34 6 17 32 40 21 10 27 12 9 31 7 13 4 24 29 8 11 2 5 15 18 35 28 30 20 33 38 42 14 |
|||
11 13 23 30 25 41 6 31 14 32 27 36 19 17 10 33 21 15 7 5 8 28 16 35 34 42 40 2 38 39 9 26 20 24 37 4 18 3 22 1 12 29 |
|||
24 17 29 38 23 39 32 5 11 15 35 12 8 10 40 1 22 25 2 36 28 4 42 21 9 20 3 31 16 41 13 30 19 34 33 18 27 6 7 37 14 26 |
|||
36 4 6 24 12 20 2 34 40 11 32 9 28 8 38 21 5 31 42 17 14 29 19 22 25 15 7 18 30 26 1 13 16 41 23 39 37 33 3 35 10 27 |
|||
20 39 2 12 32 7 22 3 17 10 37 6 18 40 27 5 42 35 28 4 24 14 33 29 30 31 26 13 19 23 36 41 1 21 9 11 15 8 34 16 25 38 |
|||
35 18 37 6 5 13 29 8 24 19 38 34 12 31 21 10 33 7 3 41 15 42 20 11 27 40 16 14 23 1 4 2 22 32 28 9 25 30 26 39 36 17 |
|||
10 32 9 33 39 19 41 38 35 18 28 26 14 30 7 4 1 22 37 21 31 40 27 15 42 34 2 25 5 12 23 36 8 6 17 3 29 24 11 13 20 16 |
|||
13 28 39 2 31 8 9 37 21 16 40 19 42 36 41 3 12 14 20 10 17 34 1 33 32 35 25 30 18 38 15 11 24 23 6 26 4 5 29 7 27 22 |
|||
7 40 12 39 18 3 16 21 42 17 1 32 5 33 13 6 41 8 29 14 34 35 24 36 38 25 31 28 26 27 20 37 23 2 30 10 22 9 19 4 11 15 |
|||
4 21 7 17 35 34 19 25 12 42 11 1 30 28 36 26 32 23 14 29 2 20 8 41 24 27 22 15 10 18 37 9 39 38 13 6 3 16 31 40 5 33 |
|||
34 23 42 14 41 27 37 6 9 31 4 5 7 1 25 16 35 30 33 11 19 3 26 12 17 38 8 20 24 13 29 15 32 28 40 22 2 39 18 36 21 10 |
|||
30 6 21 9 20 17 5 32 38 13 12 28 16 35 22 36 34 29 40 39 25 15 14 37 33 11 4 41 1 2 19 3 26 27 42 8 10 7 23 31 24 18 |
|||
6 38 8 10 42 35 13 1 16 37 21 3 11 34 32 20 29 18 25 22 36 5 30 26 39 23 28 12 2 31 7 19 33 40 14 24 9 41 17 27 15 4 |
|||
29 15 1 21 14 11 26 17 30 38 10 33 36 20 4 18 39 16 31 3 35 2 32 28 19 13 42 7 12 8 6 40 5 9 25 37 24 27 41 23 22 34 |
|||
21 36 32 8 6 23 15 19 2 14 18 4 3 11 5 28 26 13 34 25 30 17 7 42 16 22 39 40 29 37 33 12 41 10 27 31 35 38 24 20 9 1 |
|||
39 20 31 29 19 4 38 16 27 30 24 11 2 3 33 15 8 28 18 37 10 13 9 23 36 1 17 22 25 32 26 35 12 42 34 7 40 14 21 5 6 41 |
|||
12 11 17 42 9 2 14 7 22 24 25 31 38 41 15 19 36 33 32 28 1 10 29 40 23 18 37 39 6 21 35 27 3 16 8 30 5 26 4 34 13 20 |
|||
18 29 33 16 27 42 40 26 7 8 39 24 41 5 30 38 6 9 13 1 32 22 2 34 12 37 11 10 35 20 14 17 21 4 15 19 23 36 28 25 31 3 |
|||
28 2 4 18 11 5 23 20 25 35 42 30 31 14 3 9 24 27 19 7 22 6 12 10 1 32 41 36 21 33 16 34 29 13 39 15 38 17 37 26 40 8 |
|||
3 26 11 35 24 37 17 36 6 7 13 41 4 32 9 2 31 34 22 15 29 8 40 18 21 5 27 1 14 16 10 38 25 33 20 12 19 42 39 28 30 23 |
|||
31 5 22 27 10 6 8 13 34 2 33 7 32 42 26 12 19 4 15 9 40 16 28 38 37 39 35 24 20 29 17 23 11 14 3 25 41 21 36 18 1 30 |
|||
15 24 5 37 3 28 7 22 19 34 20 18 17 12 23 8 25 11 36 16 27 41 10 4 31 2 9 32 33 42 21 14 13 29 38 35 26 1 30 6 39 40 |
|||
27 37 25 5 13 16 24 41 28 3 2 10 23 4 14 30 11 38 6 19 26 32 21 20 40 9 33 35 34 22 42 8 18 17 12 36 31 15 1 29 7 39 |
|||
26 30 10 3 36 22 33 11 5 20 29 21 13 25 31 37 17 2 9 35 18 27 23 39 14 19 32 16 28 6 8 42 4 12 1 38 7 34 40 15 41 24 |
|||
32 8 18 31 1 14 34 12 33 28 17 39 37 9 19 27 7 5 30 24 20 23 11 25 15 36 21 6 22 40 41 16 10 26 4 2 42 35 38 3 29 13 |
|||
9 14 40 23 37 38 18 15 20 12 36 8 1 22 28 24 27 42 4 32 6 11 41 19 26 10 13 21 7 25 30 29 34 39 2 16 33 31 5 17 3 35 |
|||
22 12 15 4 34 1 39 42 32 40 7 35 20 29 11 25 9 6 24 26 37 19 17 16 8 21 14 38 27 28 3 33 30 31 18 5 36 13 10 41 23 2 |
|||
40 1 38 20 29 12 28 18 26 21 23 16 24 37 6 41 15 19 27 8 3 39 22 9 7 17 10 33 4 35 31 25 2 30 36 34 14 11 13 42 32 5 |
|||
</pre> |
|||