Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: First version now far quicker thanks to advice by Nigel Galloway and second version removed as no longer necessary.)
(→‎{{header|F_Sharp|F#}}: i' j' and z' are idiotmatic F# but Rosettacode's syntax highlighting doesn't cope)
Line 19: Line 19:
<lang fsharp>
<lang fsharp>
// Jacobson and Matthews technique for generating Latin Squares. Nigel Galloway: August 5th., 2019
// 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 jmLS α X0=
let X0=Array2D.copy X0
let X0=Array2D.copy X0
let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2])
let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2])
let rec randLS i j z i' j' z'=
let rec randLS i j z n g s=
X0.[i,j']<-z'; X0.[i',j]<-z'
X0.[i,g]<-s; X0.[n,j]<-s
match X0.[i',j']=z' with
if X0.[n,g]=s then X0.[n,g]<-z; X0
⚫
else randLS n g s (List.find(fun n->X0.[n,g]=s)(N())) (List.find(fun g->X0.[n,g]=s)(N())) (if (R 2)=0 then let t=X0.[n,g] in X0.[n,g]<-z; t else z)
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 i,j=R α,R α
let z =let z=1+(R (α-1)) in if z<X0.[i,j] then z else 1+(z+1)%α
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])
let n,g,s=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'
X0.[i,j]<-z; randLS i j z n g s


let asNormLS α=
let asNormLS α=
Line 69: Line 67:
;part 2
;part 2
<lang fsharp>
<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 ""
randLS 5 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iteri(fun n g->printf "%d(%d) " (n+1) (snd g)); printfn ""
</lang>
</lang>
{{out}}
{{out}}
Line 124: Line 122:
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
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
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>

;part 4
Generating 1000 Latin Squares of order 256 takes about 1.5secs
<lang fsharp>
printfn "%d" (Array2D.length1 (Seq.item 999 (randLS 256)))
</lang>
{{out}}
<pre>
256
Real: 00:00:01.512, CPU: 00:00:01.970, GC gen0: 10, gen1: 10
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Latin_Squares_in_reduced_form/Randomizing_using_Jacobson_and_Matthews’_Technique"