Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions
Content added Content deleted
(added Raku programming solution) |
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) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
#REDIRECT [[Latin Squares in reduced form/Randomizing using Jacobson and Matthews' technique]] |
|||
{{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 n g s= |
|||
X0.[i,g]<-s; X0.[n,j]<-s |
|||
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) |
|||
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 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 n g s |
|||
let asNormLS α= |
|||
let n=Array.init (Array2D.length1 α) (fun n->(α.[n,0]-1,n))|>Map.ofArray |
|||
let g=Array.init (Array2D.length1 α) (fun g->(α.[n.[0],g]-1,g))|>Map.ofArray |
|||
Array2D.init (Array2D.length1 α) (Array2D.length1 α) (fun i j->α.[n.[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 5 |> 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> |
|||
;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> |
|||
=={{header|Go}}== |
|||
The J & M implementation is based on the C code [https://brainwagon.org/2016/05/17/code-for-generating-a-random-latin-square/ here] which has been heavily optimized following advice and clarification by Nigel Galloway (see Talk page) on the requirements of this task. |
|||
Part 4 is taking about 6.5 seconds on my Celeron @1.6 GHz but will be much faster on a more modern machine. Being able to compute random, uniformly distributed, Latin squares of order 256 reasonably quickly is interesting from a secure communications or cryptographic standpoint as the symbols of such a square can represent the 256 characters of the various extended ASCII encodings. |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math/rand" |
|||
"time" |
|||
) |
|||
type ( |
|||
vector []int |
|||
matrix []vector |
|||
cube []matrix |
|||
) |
|||
func toReduced(m matrix) matrix { |
|||
n := len(m) |
|||
r := make(matrix, n) |
|||
for i := 0; i < n; i++ { |
|||
r[i] = make(vector, n) |
|||
copy(r[i], m[i]) |
|||
} |
|||
for j := 0; j < n-1; j++ { |
|||
if r[0][j] != j { |
|||
for k := j + 1; k < n; k++ { |
|||
if r[0][k] == j { |
|||
for i := 0; i < n; i++ { |
|||
r[i][j], r[i][k] = r[i][k], r[i][j] |
|||
} |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
for i := 1; i < n-1; i++ { |
|||
if r[i][0] != i { |
|||
for k := i + 1; k < n; k++ { |
|||
if r[k][0] == i { |
|||
for j := 0; j < n; j++ { |
|||
r[i][j], r[k][j] = r[k][j], r[i][j] |
|||
} |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return r |
|||
} |
|||
// 'm' is assumed to be 0 based |
|||
func printMatrix(m matrix) { |
|||
n := len(m) |
|||
for i := 0; i < n; i++ { |
|||
for j := 0; j < n; j++ { |
|||
fmt.Printf("%2d ", m[i][j]+1) // back to 1 based |
|||
} |
|||
fmt.Println() |
|||
} |
|||
fmt.Println() |
|||
} |
|||
// converts 4 x 4 matrix to 'flat' array |
|||
func asArray16(m matrix) [16]int { |
|||
var a [16]int |
|||
k := 0 |
|||
for i := 0; i < 4; i++ { |
|||
for j := 0; j < 4; j++ { |
|||
a[k] = m[i][j] |
|||
k++ |
|||
} |
|||
} |
|||
return a |
|||
} |
|||
// converts 5 x 5 matrix to 'flat' array |
|||
func asArray25(m matrix) [25]int { |
|||
var a [25]int |
|||
k := 0 |
|||
for i := 0; i < 5; i++ { |
|||
for j := 0; j < 5; j++ { |
|||
a[k] = m[i][j] |
|||
k++ |
|||
} |
|||
} |
|||
return a |
|||
} |
|||
// 'a' is assumed to be 0 based |
|||
func printArray16(a [16]int) { |
|||
for i := 0; i < 4; i++ { |
|||
for j := 0; j < 4; j++ { |
|||
k := i*4 + j |
|||
fmt.Printf("%2d ", a[k]+1) // back to 1 based |
|||
} |
|||
fmt.Println() |
|||
} |
|||
fmt.Println() |
|||
} |
|||
func shuffleCube(c cube) { |
|||
n := len(c[0]) |
|||
proper := true |
|||
var rx, ry, rz int |
|||
for { |
|||
rx = rand.Intn(n) |
|||
ry = rand.Intn(n) |
|||
rz = rand.Intn(n) |
|||
if c[rx][ry][rz] == 0 { |
|||
break |
|||
} |
|||
} |
|||
for { |
|||
var ox, oy, oz int |
|||
for ; ox < n; ox++ { |
|||
if c[ox][ry][rz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
if !proper && rand.Intn(2) == 0 { |
|||
for ox++; ox < n; ox++ { |
|||
if c[ox][ry][rz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
} |
|||
for ; oy < n; oy++ { |
|||
if c[rx][oy][rz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
if !proper && rand.Intn(2) == 0 { |
|||
for oy++; oy < n; oy++ { |
|||
if c[rx][oy][rz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
} |
|||
for ; oz < n; oz++ { |
|||
if c[rx][ry][oz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
if !proper && rand.Intn(2) == 0 { |
|||
for oz++; oz < n; oz++ { |
|||
if c[rx][ry][oz] == 1 { |
|||
break |
|||
} |
|||
} |
|||
} |
|||
c[rx][ry][rz]++ |
|||
c[rx][oy][oz]++ |
|||
c[ox][ry][oz]++ |
|||
c[ox][oy][rz]++ |
|||
c[rx][ry][oz]-- |
|||
c[rx][oy][rz]-- |
|||
c[ox][ry][rz]-- |
|||
c[ox][oy][oz]-- |
|||
if c[ox][oy][oz] < 0 { |
|||
rx, ry, rz = ox, oy, oz |
|||
proper = false |
|||
} else { |
|||
proper = true |
|||
break |
|||
} |
|||
} |
|||
} |
|||
func toMatrix(c cube) matrix { |
|||
n := len(c[0]) |
|||
m := make(matrix, n) |
|||
for i := 0; i < n; i++ { |
|||
m[i] = make(vector, n) |
|||
} |
|||
for i := 0; i < n; i++ { |
|||
for j := 0; j < n; j++ { |
|||
for k := 0; k < n; k++ { |
|||
if c[i][j][k] != 0 { |
|||
m[i][j] = k |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return m |
|||
} |
|||
// 'from' matrix is assumed to be 1 based |
|||
func makeCube(from matrix, n int) cube { |
|||
c := make(cube, n) |
|||
for i := 0; i < n; i++ { |
|||
c[i] = make(matrix, n) |
|||
for j := 0; j < n; j++ { |
|||
c[i][j] = make(vector, n) |
|||
var k int |
|||
if from == nil { |
|||
k = (i + j) % n |
|||
} else { |
|||
k = from[i][j] - 1 |
|||
} |
|||
c[i][j][k] = 1 |
|||
} |
|||
} |
|||
return c |
|||
} |
|||
func main() { |
|||
rand.Seed(time.Now().UnixNano()) |
|||
// part 1 |
|||
fmt.Println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n") |
|||
from := matrix{{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}} |
|||
freqs4 := make(map[[16]int]int, 10000) |
|||
c := makeCube(from, 4) |
|||
for i := 1; i <= 10000; i++ { |
|||
shuffleCube(c) |
|||
m := toMatrix(c) |
|||
rm := toReduced(m) |
|||
a16 := asArray16(rm) |
|||
freqs4[a16]++ |
|||
} |
|||
for a, freq := range freqs4 { |
|||
printArray16(a) |
|||
fmt.Printf("Occurs %d times\n\n", freq) |
|||
} |
|||
// part 2 |
|||
fmt.Println("\nPART 2: 10,000 latin squares of order 5 in reduced form:") |
|||
from = matrix{{1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 1, 2}, |
|||
{4, 5, 1, 2, 3}, {5, 1, 2, 3, 4}} |
|||
freqs5 := make(map[[25]int]int, 10000) |
|||
c = makeCube(from, 5) |
|||
for i := 1; i <= 10000; i++ { |
|||
shuffleCube(c) |
|||
m := toMatrix(c) |
|||
rm := toReduced(m) |
|||
a25 := asArray25(rm) |
|||
freqs5[a25]++ |
|||
} |
|||
count := 0 |
|||
for _, freq := range freqs5 { |
|||
count++ |
|||
if count > 1 { |
|||
fmt.Print(", ") |
|||
} |
|||
if (count-1)%8 == 0 { |
|||
fmt.Println() |
|||
} |
|||
fmt.Printf("%2d(%3d)", count, freq) |
|||
} |
|||
fmt.Println("\n") |
|||
// part 3 |
|||
fmt.Println("\nPART 3: 750 latin squares of order 42, showing the last one:\n") |
|||
var m42 matrix |
|||
c = makeCube(nil, 42) |
|||
for i := 1; i <= 750; i++ { |
|||
shuffleCube(c) |
|||
if i == 750 { |
|||
m42 = toMatrix(c) |
|||
} |
|||
} |
|||
printMatrix(m42) |
|||
// part 4 |
|||
fmt.Println("\nPART 4: 1000 latin squares of order 256:\n") |
|||
start := time.Now() |
|||
c = makeCube(nil, 256) |
|||
for i := 1; i <= 1000; i++ { |
|||
shuffleCube(c) |
|||
} |
|||
elapsed := time.Since(start) |
|||
fmt.Printf("Generated in %s\n", elapsed) |
|||
}</lang> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
PART 1: 10,000 latin Squares of order 4 in reduced form: |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 2 1 |
|||
4 3 1 2 |
|||
Occurs 2550 times |
|||
1 2 3 4 |
|||
2 4 1 3 |
|||
3 1 4 2 |
|||
4 3 2 1 |
|||
Occurs 2430 times |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 1 2 |
|||
4 3 2 1 |
|||
Occurs 2494 times |
|||
1 2 3 4 |
|||
2 3 4 1 |
|||
3 4 1 2 |
|||
4 1 2 3 |
|||
Occurs 2526 times |
|||
PART 2: 10,000 latin squares of order 5 in reduced form: |
|||
1(165), 2(173), 3(167), 4(204), 5(173), 6(165), 7(215), 8(218), |
|||
9(168), 10(157), 11(205), 12(152), 13(187), 14(173), 15(215), 16(185), |
|||
17(179), 18(176), 19(179), 20(160), 21(150), 22(166), 23(191), 24(181), |
|||
25(179), 26(192), 27(187), 28(186), 29(176), 30(196), 31(141), 32(187), |
|||
33(165), 34(189), 35(147), 36(175), 37(172), 38(162), 39(180), 40(172), |
|||
41(189), 42(159), 43(197), 44(158), 45(178), 46(179), 47(193), 48(175), |
|||
49(207), 50(174), 51(181), 52(179), 53(193), 54(171), 55(153), 56(204) |
|||
PART 3: 750 latin squares of order 42, showing the last one: |
|||
29 2 17 41 34 30 8 33 39 7 20 27 12 6 31 14 40 35 25 9 10 32 19 16 24 42 3 26 5 23 1 28 4 13 38 18 21 37 22 15 36 11 |
|||
17 15 11 31 9 38 26 10 1 28 37 8 34 41 21 22 12 5 35 36 13 20 29 42 18 3 19 24 39 32 27 23 16 25 33 4 40 6 2 30 7 14 |
|||
36 42 35 39 15 34 37 18 32 25 22 31 4 17 3 19 13 11 8 23 12 24 28 27 16 1 6 9 29 40 7 5 2 14 30 26 41 10 21 33 38 20 |
|||
21 13 16 42 3 32 2 26 27 17 15 11 25 37 29 6 19 10 12 7 31 18 36 9 39 41 30 40 35 33 22 1 28 38 24 8 34 23 4 20 14 5 |
|||
22 39 13 7 38 9 34 41 37 36 35 6 21 26 17 16 4 30 40 20 8 15 25 19 32 2 11 28 23 24 31 10 42 3 27 12 33 14 1 29 5 18 |
|||
33 36 34 3 13 4 7 14 2 29 6 12 31 23 26 17 8 20 32 21 19 41 37 5 38 30 25 11 24 35 42 27 18 16 39 15 10 22 28 1 9 40 |
|||
14 31 7 22 39 23 32 34 16 33 24 4 40 42 12 25 35 26 18 28 11 3 15 21 20 9 13 19 1 10 2 41 29 6 17 30 5 38 37 8 27 36 |
|||
9 3 6 30 19 39 14 16 4 15 29 28 23 24 32 10 18 41 37 38 40 34 8 25 2 22 31 5 17 26 36 33 13 21 12 35 7 20 11 27 42 1 |
|||
2 18 28 5 6 7 40 35 3 20 8 34 42 39 37 33 26 23 22 13 14 4 12 15 17 25 36 31 16 29 38 19 32 41 1 27 24 11 30 9 10 21 |
|||
27 34 19 15 33 22 5 36 9 30 14 1 24 8 38 42 41 39 7 40 4 37 11 23 29 26 18 12 3 21 35 16 20 10 31 25 17 28 6 32 2 13 |
|||
41 16 1 35 22 13 20 29 6 38 5 24 19 10 25 27 17 18 11 32 9 7 2 36 4 34 40 21 33 12 8 30 15 42 37 23 14 26 3 39 31 28 |
|||
7 1 15 16 27 31 18 24 20 8 36 38 10 34 9 4 42 29 2 3 26 39 5 22 41 21 37 30 14 11 33 35 25 23 40 28 13 19 17 6 32 12 |
|||
1 10 20 32 23 5 30 12 8 9 21 36 15 14 18 37 33 31 26 39 41 16 6 24 22 35 29 42 27 28 3 38 11 2 7 34 4 40 19 17 13 25 |
|||
6 32 42 11 20 40 27 25 41 22 17 16 26 29 15 7 23 36 39 34 28 13 18 3 10 37 8 14 2 31 4 24 5 19 9 21 38 1 33 12 30 35 |
|||
35 40 30 19 21 12 17 4 22 27 3 20 11 9 8 23 24 42 14 10 39 28 26 29 33 13 41 16 34 25 32 37 7 18 5 6 15 2 36 38 1 31 |
|||
15 26 40 1 28 20 9 21 7 5 13 18 30 22 10 8 3 25 6 2 17 36 38 31 14 19 35 23 12 27 11 39 24 4 41 32 29 34 42 16 37 33 |
|||
3 6 26 12 32 1 13 8 42 37 25 7 9 16 35 5 29 21 24 27 34 17 14 2 15 11 28 33 20 38 18 22 39 40 23 10 31 30 41 36 19 4 |
|||
31 38 36 21 16 26 28 30 15 3 32 41 18 1 6 29 9 17 5 35 7 40 27 37 13 20 23 22 11 19 12 42 34 8 10 14 25 39 24 4 33 2 |
|||
40 4 22 38 35 11 21 17 31 1 28 19 37 2 42 24 14 12 13 30 33 25 34 32 27 36 39 3 9 15 10 18 8 5 6 41 26 16 29 7 20 23 |
|||
5 17 39 4 26 14 31 37 35 11 38 3 1 30 19 36 20 33 15 16 21 29 9 6 25 27 2 13 41 34 24 12 10 32 22 7 28 18 40 42 23 8 |
|||
8 29 24 26 31 21 39 23 11 14 19 10 20 15 7 35 32 38 1 12 25 22 16 4 6 40 42 41 18 30 28 2 17 36 3 13 37 33 27 5 34 9 |
|||
11 25 14 17 18 24 19 32 33 31 7 26 2 21 20 30 15 27 23 41 29 35 39 28 34 12 10 4 8 42 5 13 37 9 16 40 1 36 38 3 6 22 |
|||
26 21 18 25 29 15 1 13 19 2 34 23 38 27 41 3 10 22 17 4 16 11 42 12 8 6 5 35 30 39 37 14 9 24 36 33 20 7 31 28 40 32 |
|||
25 27 12 33 17 35 24 9 28 10 42 21 8 13 2 15 34 16 3 18 5 31 41 7 23 4 1 6 22 14 19 36 40 37 26 38 30 32 20 11 39 29 |
|||
23 19 25 9 30 37 38 40 14 41 31 17 7 4 16 11 1 6 33 5 24 2 3 8 21 29 34 32 28 22 15 20 12 35 18 36 39 27 10 13 26 42 |
|||
34 9 10 13 2 6 22 31 26 40 1 14 41 3 11 12 37 32 27 29 35 19 30 33 28 38 21 25 7 5 16 8 36 15 20 42 23 17 39 18 4 24 |
|||
20 11 37 28 41 8 10 15 36 12 26 33 39 32 13 1 25 9 42 19 3 6 24 14 5 23 7 27 38 2 30 4 22 34 35 31 18 29 16 40 21 17 |
|||
28 30 21 23 24 29 3 1 10 6 33 2 27 40 14 34 31 15 19 37 18 9 4 13 35 8 12 20 36 16 17 32 41 7 25 39 42 5 26 22 11 38 |
|||
32 12 8 40 11 16 23 28 18 42 41 30 3 38 33 2 22 19 4 25 37 1 31 20 36 5 9 7 13 17 14 6 27 39 34 24 35 21 15 26 29 10 |
|||
18 37 41 10 36 28 11 42 13 34 2 35 5 7 22 40 39 3 30 1 38 27 20 17 19 33 26 15 25 6 21 29 23 31 4 9 32 8 12 14 24 16 |
|||
39 24 29 37 25 19 33 27 17 16 10 40 36 12 30 41 11 4 34 15 2 5 32 1 31 14 38 18 42 3 9 7 6 20 21 22 8 13 23 35 28 26 |
|||
19 14 5 8 40 3 29 6 21 26 23 15 16 33 28 31 38 13 9 17 27 12 10 11 7 24 20 1 4 41 39 25 30 22 32 2 36 42 35 34 18 37 |
|||
37 7 32 34 8 36 41 2 12 24 16 39 33 31 4 13 6 28 38 22 20 42 40 18 9 10 14 29 26 1 23 15 21 27 19 17 11 3 5 25 35 30 |
|||
4 41 27 2 42 17 15 38 30 35 12 25 13 28 39 20 5 1 16 33 36 23 7 40 37 32 24 10 31 8 6 21 14 26 29 11 3 9 18 19 22 34 |
|||
38 35 23 36 4 10 12 11 5 21 27 32 17 25 24 18 28 40 20 6 42 14 22 30 26 39 33 8 37 7 13 34 1 29 15 19 2 41 9 31 16 3 |
|||
30 33 31 24 12 41 36 19 23 32 4 37 29 11 34 39 16 14 21 42 6 26 1 38 3 17 22 2 40 18 20 9 35 28 13 5 27 15 25 10 8 7 |
|||
42 28 3 14 1 25 16 22 34 23 39 9 35 5 40 26 36 7 10 31 32 21 13 41 30 18 4 38 6 37 29 17 33 12 11 20 19 24 8 2 15 27 |
|||
16 5 38 6 10 27 4 3 40 18 11 13 22 35 1 21 2 34 36 8 23 30 17 39 42 7 15 37 32 20 26 31 19 33 28 29 9 25 14 24 12 41 |
|||
24 23 33 18 14 2 25 39 29 19 9 5 28 20 27 38 7 8 31 11 15 10 35 34 12 16 32 17 21 36 40 3 26 30 42 1 22 4 13 37 41 6 |
|||
12 20 2 29 5 33 42 7 24 4 18 22 14 19 36 9 27 37 28 26 30 38 23 10 11 31 17 34 15 13 41 40 3 1 8 16 6 35 32 21 25 39 |
|||
13 8 9 27 37 42 6 20 25 39 40 29 32 18 5 28 30 24 41 14 22 33 21 35 1 15 16 36 10 4 34 26 38 11 2 3 12 31 7 23 17 19 |
|||
10 22 4 20 7 18 35 5 38 13 30 42 6 36 23 32 21 2 29 24 1 8 33 26 40 28 27 39 19 9 25 11 31 17 14 37 16 12 34 41 3 15 |
|||
PART 4: 1000 latin squares of order 256: |
|||
Generated in 6.581088256s |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{trans|Go}} |
|||
<lang julia>const Cube = Vector{Vector{Vector{Int}}} |
|||
const Mat = Vector{Vector{Int}} |
|||
function reduced(m::Mat) |
|||
n = length(m) |
|||
r = deepcopy(m) |
|||
for j in 1:n-1 |
|||
if r[1][j] != j |
|||
for k in j+1:n |
|||
if r[1][k] == j |
|||
for i in 1:n |
|||
r[i][j], r[i][k] = r[i][k], r[i][j] |
|||
end |
|||
break |
|||
end |
|||
end |
|||
end |
|||
end |
|||
for i in 2:n-1 |
|||
if r[i][1] != i |
|||
for k in i+1:n |
|||
if r[k][1] == i |
|||
for j in 1:n |
|||
r[i][j], r[k][j] = r[k][j], r[i][j] |
|||
end |
|||
break |
|||
end |
|||
end |
|||
end |
|||
end |
|||
return r |
|||
end |
|||
""" print matrix as small integers, no punctuation """ |
|||
function print_matrix(m::Mat) |
|||
n = length(m) |
|||
padding = max(2, Int(ceil(log(10, n+1))) + 1) |
|||
for i in 1:n |
|||
for j in 1:n |
|||
print(lpad(m[i][j], padding)) |
|||
end |
|||
println() |
|||
end |
|||
println() |
|||
end |
|||
function shuffle_cube(c::Cube) |
|||
n = length(c) |
|||
proper = true |
|||
rx, ry, rz = 0, 0, 0 |
|||
while true |
|||
rx, ry, rz = rand(1:n, 3) |
|||
c[rx][ry][rz] == 0 && break |
|||
end |
|||
while true |
|||
ox = something(findfirst(i -> c[i][ry][rz] == 1, 1:n), n) |
|||
oy = something(findfirst(i -> c[rx][i][rz] == 1, 1:n), n) |
|||
oz = something(findfirst(i -> c[rx][ry][i] == 1, 1:n), n) |
|||
if !proper |
|||
rand() < 1/2 && (ox = something(findlast(i -> c[i][ry][rz] == 1, 1:n), n)) |
|||
rand() < 1/2 && (oy = something(findlast(i -> c[rx][i][rz] == 1, 1:n), n)) |
|||
rand() < 1/2 && (oz = something(findlast(i -> c[rx][ry][i] == 1, 1:n), n)) |
|||
end |
|||
c[rx][ry][rz] += 1 |
|||
c[rx][oy][oz] += 1 |
|||
c[ox][ry][oz] += 1 |
|||
c[ox][oy][rz] += 1 |
|||
c[rx][ry][oz] -= 1 |
|||
c[rx][oy][rz] -= 1 |
|||
c[ox][ry][rz] -= 1 |
|||
c[ox][oy][oz] -= 1 |
|||
if c[ox][oy][oz] < 0 |
|||
rx, ry, rz = ox, oy, oz |
|||
proper = false |
|||
else |
|||
break |
|||
end |
|||
end |
|||
end |
|||
function matrix(c::Cube)::Mat |
|||
n = length(c) |
|||
m = [[0 for i in 1:n] for j in 1:n] |
|||
for i in 1:n, j in 1:n |
|||
for k in 1:n |
|||
if c[i][j][k] != 0 |
|||
m[i][j] = k |
|||
break |
|||
end |
|||
end |
|||
end |
|||
return m |
|||
end |
|||
function cube(from, n) |
|||
c = [[[0 for i in 1:n] for j in 1:n] for k in 1:n] |
|||
for i in 1:n, j in 1:n |
|||
k = (from isa Nothing) ? mod1(i + j, n) : from[i][j] |
|||
c[i][j][k] = 1 |
|||
end |
|||
return c |
|||
end |
|||
function testJacobsenMatthews() |
|||
# part 1 |
|||
println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n") |
|||
from = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]] |
|||
freqs4 = Dict{Array, Int}() |
|||
c = cube(from, 4) |
|||
for i in 1:10000 |
|||
shuffle_cube(c) |
|||
m = matrix(c) |
|||
rm = reduced(m) |
|||
n = get!(freqs4, rm, 0) |
|||
freqs4[rm] = n + 1 |
|||
end |
|||
for (a, freq) in freqs4 |
|||
print_matrix(a) |
|||
println("Occurs $freq times\n") |
|||
end |
|||
# part 2 |
|||
println("\nPART 2: 10,000 latin squares of order 5 in reduced form:\n") |
|||
from = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4]] |
|||
freqs5 = Dict{Array, Int}() |
|||
c = cube(from, 5) |
|||
for i in 1:10000 |
|||
shuffle_cube(c) |
|||
m = matrix(c) |
|||
rm = reduced(m) |
|||
n = get!(freqs5, rm, 0) |
|||
freqs5[rm] = n + 1 |
|||
end |
|||
for (i, freq) in enumerate(sort(collect(values(freqs5)))) |
|||
i > 1 && (print(", "); (i - 1) % 8 == 0 && println()) |
|||
print(lpad(i, 2), "(", lpad(freq, 3), ")") |
|||
end |
|||
println("\n") |
|||
# part 3 |
|||
println("\nPART 3: 750 latin squares of order 42, showing the last one:\n") |
|||
m42 = [[0 for i in 1:42] for j in 1:42] |
|||
c = cube(nothing, 42) |
|||
for i in 1:750 |
|||
shuffle_cube(c) |
|||
i == 750 && (m42 = matrix(c)) |
|||
end |
|||
print_matrix(m42) |
|||
# part 4 |
|||
println("\nPART 4: 1000 latin squares of order 256:\n") |
|||
@time begin |
|||
c = cube(nothing, 256) |
|||
for i in 1:1000 |
|||
shuffle_cube(c) |
|||
end |
|||
end |
|||
end |
|||
testJacobsenMatthews() |
|||
</lang>{{out}} |
|||
<pre> |
|||
PART 1: 10,000 latin Squares of order 4 in reduced form: |
|||
1 2 3 4 |
|||
2 4 1 3 |
|||
3 1 4 2 |
|||
4 3 2 1 |
|||
Occurs 2508 times |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 2 1 |
|||
4 3 1 2 |
|||
Occurs 2427 times |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 1 2 |
|||
4 3 2 1 |
|||
Occurs 2529 times |
|||
1 2 3 4 |
|||
2 3 4 1 |
|||
3 4 1 2 |
|||
4 1 2 3 |
|||
Occurs 2536 times |
|||
PART 2: 10,000 latin squares of order 5 in reduced form: |
|||
1(152), 2(152), 3(153), 4(154), 5(158), 6(160), 7(160), 8(160), |
|||
9(162), 10(165), 11(166), 12(167), 13(168), 14(170), 15(170), 16(172), |
|||
17(172), 18(173), 19(174), 20(174), 21(175), 22(177), 23(177), 24(177), |
|||
25(177), 26(178), 27(179), 28(180), 29(180), 30(181), 31(181), 32(182), |
|||
33(182), 34(182), 35(183), 36(184), 37(185), 38(185), 39(185), 40(186), |
|||
41(187), 42(187), 43(187), 44(188), 45(189), 46(189), 47(190), 48(195), |
|||
49(195), 50(197), 51(197), 52(199), 53(199), 54(199), 55(201), 56(203) |
|||
PART 3: 750 latin squares of order 42, showing the last one: |
|||
32 34 23 19 7 42 37 4 38 2 26 25 17 16 22 20 18 8 28 24 40 35 3 33 6 1 41 36 13 39 10 14 9 30 27 29 15 5 12 11 21 31 |
|||
19 16 27 14 4 15 31 8 36 3 34 18 2 10 30 42 22 35 41 21 13 5 11 29 37 39 9 12 32 7 33 17 28 40 25 26 23 24 38 6 1 20 |
|||
22 7 11 41 14 27 4 3 30 39 38 40 23 36 19 5 25 13 29 37 33 8 15 32 16 34 6 42 24 1 28 18 21 10 9 35 17 20 2 26 31 12 |
|||
18 26 38 24 25 14 6 39 40 5 13 21 20 34 29 4 3 22 30 42 12 19 23 8 32 17 7 27 35 28 2 31 15 41 10 36 11 9 1 37 16 33 |
|||
37 24 21 15 30 36 2 27 4 11 6 16 26 38 14 31 9 34 39 1 8 41 40 42 17 3 18 33 12 13 22 23 19 35 7 5 25 32 28 10 20 29 |
|||
8 38 22 21 26 28 12 37 10 41 35 34 13 24 27 16 2 17 20 6 7 30 42 39 40 4 1 18 36 3 15 33 5 29 19 11 32 25 14 31 23 9 |
|||
31 35 2 8 10 39 13 22 20 14 15 24 16 30 21 40 36 4 1 3 23 25 29 26 5 32 33 38 9 37 11 19 18 42 17 41 12 6 34 7 27 28 |
|||
29 10 35 4 39 13 5 12 21 18 37 14 40 17 33 7 30 25 2 11 34 22 41 15 3 9 38 31 26 16 32 36 27 19 8 1 20 28 23 24 6 42 |
|||
5 14 37 16 19 10 21 17 18 23 29 42 12 11 4 34 35 38 6 28 3 27 9 24 8 30 26 2 41 25 1 13 7 32 36 15 39 31 20 40 33 22 |
|||
13 28 31 2 37 7 34 9 24 38 1 30 3 14 40 35 20 12 23 19 4 11 27 25 26 10 15 17 42 36 18 5 22 39 16 6 29 41 21 33 8 32 |
|||
7 19 24 10 9 30 15 42 26 34 28 32 36 4 11 41 40 27 13 23 31 18 14 3 20 12 5 1 38 29 35 39 16 8 2 21 37 33 25 17 22 6 |
|||
28 22 36 6 21 20 16 34 32 29 8 27 18 42 26 24 12 30 5 39 14 10 4 19 15 31 25 9 40 41 38 2 33 23 35 7 1 37 11 13 3 17 |
|||
16 23 30 33 18 38 22 5 41 9 4 12 35 13 37 32 11 6 19 10 42 31 20 1 2 7 17 21 28 15 34 40 29 36 3 14 8 27 24 39 25 26 |
|||
20 12 41 13 38 21 23 29 17 10 30 2 25 8 42 3 4 24 18 35 11 40 33 36 22 26 32 19 1 6 14 28 37 31 34 9 27 7 39 16 15 5 |
|||
15 36 34 26 1 18 28 6 31 37 17 20 29 41 35 22 10 33 25 32 21 3 7 16 14 42 27 24 5 19 4 11 39 13 40 38 30 23 9 12 2 8 |
|||
36 42 1 31 13 3 39 32 27 4 23 28 7 2 18 11 6 19 26 16 22 15 12 41 21 5 34 40 25 38 37 20 30 17 29 8 33 14 10 9 24 35 |
|||
33 8 3 7 29 9 40 28 2 19 5 13 15 26 39 37 32 1 14 17 38 4 21 27 41 6 23 34 10 12 36 30 35 24 20 25 42 22 31 18 11 16 |
|||
21 37 12 9 17 2 29 16 34 7 3 19 42 40 5 33 31 28 36 8 18 23 22 6 10 41 30 39 20 11 24 25 38 15 13 27 26 4 35 32 14 1 |
|||
1 32 29 35 22 40 7 23 28 26 18 37 6 20 16 19 14 9 17 33 41 24 31 38 34 25 12 3 30 2 8 27 36 11 39 42 4 10 5 21 13 15 |
|||
42 30 4 18 24 33 27 35 12 16 32 15 41 5 10 6 13 11 7 29 9 14 25 23 19 37 3 20 2 22 31 21 40 1 26 28 36 38 17 8 39 34 |
|||
35 5 7 36 23 6 20 15 13 25 19 17 28 32 9 1 33 40 10 26 2 12 39 4 29 38 8 16 3 14 27 24 41 22 11 30 31 21 42 34 37 18 |
|||
24 29 28 17 20 4 9 33 19 40 31 6 22 12 25 30 38 5 32 41 39 34 36 2 1 8 37 15 21 26 16 42 10 27 18 23 35 11 13 14 7 3 |
|||
30 40 32 39 35 41 14 20 9 6 10 11 4 31 13 23 16 2 3 22 36 29 24 7 25 15 21 28 17 33 12 38 34 5 1 19 18 8 26 27 42 37 |
|||
27 25 18 11 15 35 30 41 42 24 33 29 32 23 3 8 21 10 22 31 28 20 19 12 39 36 14 6 34 9 5 1 2 38 37 40 16 26 7 4 17 13 |
|||
12 13 40 42 11 26 17 30 39 36 14 4 19 18 20 2 15 7 38 25 5 16 37 21 31 35 29 8 6 27 23 32 24 9 28 22 3 1 33 41 34 10 |
|||
2 3 5 23 12 31 33 14 15 21 25 8 24 39 28 9 41 29 27 7 30 13 16 34 38 40 4 37 19 42 17 26 1 20 22 32 10 18 6 36 35 11 |
|||
25 9 39 40 33 17 26 1 29 22 24 36 37 7 15 21 8 18 16 30 6 38 35 14 23 28 10 11 27 31 13 3 42 34 4 20 41 2 32 5 12 19 |
|||
9 41 6 22 8 12 10 21 7 15 2 5 34 25 31 14 1 16 33 20 37 39 32 17 27 29 19 35 11 18 30 4 13 26 38 3 24 42 36 28 40 23 |
|||
6 21 26 29 3 24 8 18 23 42 40 33 38 9 36 27 28 14 11 5 15 7 34 37 12 2 20 4 16 10 41 35 31 25 32 17 19 13 22 1 30 39 |
|||
14 4 16 30 31 8 11 25 22 28 41 10 1 19 2 39 37 26 35 15 24 6 38 20 13 27 42 5 23 34 21 9 32 18 33 12 7 17 3 29 36 40 |
|||
11 1 25 3 5 32 35 7 8 31 36 39 30 37 24 12 34 41 42 27 10 28 6 9 18 21 2 22 29 23 20 15 17 33 14 13 40 16 4 19 26 38 |
|||
34 27 42 1 40 16 32 36 3 30 39 22 33 29 23 17 5 21 24 18 35 26 10 28 4 19 13 7 8 20 9 37 11 12 31 2 6 15 41 25 38 14 |
|||
17 39 19 32 42 23 25 2 11 1 20 35 10 3 6 36 27 37 9 13 26 21 8 22 28 33 24 14 18 40 7 29 4 16 12 31 38 34 15 30 5 41 |
|||
26 31 17 37 2 29 42 40 14 12 27 23 11 1 7 15 24 32 8 34 25 33 30 10 9 16 22 41 4 35 3 6 20 28 5 39 13 36 19 38 18 21 |
|||
4 33 13 20 41 34 18 31 1 17 16 38 27 35 8 28 23 39 15 36 19 9 26 30 42 24 11 32 14 21 25 12 3 7 6 37 5 40 29 22 10 2 |
|||
41 20 15 5 36 37 19 38 25 13 42 7 39 6 32 10 26 31 34 12 1 17 2 11 35 18 28 29 22 4 40 16 23 21 24 33 14 30 8 3 9 27 |
|||
38 18 10 34 6 11 24 26 37 27 12 3 31 28 17 13 42 15 21 14 16 32 1 40 33 23 36 25 39 5 19 22 8 2 41 4 9 35 30 20 29 7 |
|||
3 11 33 12 34 25 38 24 5 35 7 26 9 27 1 18 39 20 37 4 29 2 17 13 30 22 40 23 31 32 42 8 6 14 21 10 28 19 16 15 41 36 |
|||
40 17 20 38 27 5 3 13 33 8 22 41 21 15 12 25 29 36 31 9 32 1 28 35 11 14 16 10 37 30 6 7 26 4 42 34 2 39 18 23 19 24 |
|||
39 2 9 28 16 1 41 19 6 32 21 31 8 33 34 29 7 23 40 38 20 37 5 18 36 11 35 13 15 17 26 10 14 3 30 24 22 12 27 42 4 25 |
|||
10 15 8 27 32 22 36 11 35 20 9 1 14 21 38 26 19 3 12 40 17 42 18 5 7 13 31 30 33 24 39 41 25 6 23 16 34 29 37 2 28 4 |
|||
23 6 14 25 28 19 1 10 16 33 11 9 5 22 41 38 17 42 4 2 27 36 13 31 24 20 39 26 7 8 29 34 12 37 15 18 21 3 40 35 32 30 |
|||
PART 4: 1000 latin squares of order 256: |
|||
10.811605 seconds (745.43 k allocations: 157.305 MiB, 0.30% gc time) |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
<lang Nim>import random, sequtils, strformat, tables, times |
|||
type |
|||
Vector = seq[int] |
|||
Matrix = seq[Vector] |
|||
Cube = seq[Matrix] |
|||
Array16 = array[16, int] |
|||
Array25 = array[25, int] |
|||
func newCube(m: Matrix; n: Positive): Cube = |
|||
result.setLen(n) |
|||
for i in 0..<n: |
|||
result[i].setLen(n) |
|||
for j in 0..<n: |
|||
result[i][j].setLen(n) |
|||
let k = if m.len == 0: (i + j) mod n else: m[i][j] - 1 |
|||
result[i][j][k] = 1 |
|||
proc shuffle(c: var Cube) = |
|||
let n = c[0].len |
|||
var proper = true |
|||
var rx, ry, rz: int |
|||
while true: |
|||
rx = rand(n - 1) |
|||
ry = rand(n - 1) |
|||
rz = rand(n - 1) |
|||
if c[rx][ry][rz] == 0: break |
|||
while true: |
|||
var ox, oy, oz = 0 |
|||
while ox < n: |
|||
if c[ox][ry][rz] == 1: break |
|||
inc ox |
|||
if not proper and rand(1) == 0: |
|||
inc ox |
|||
while ox < n: |
|||
if c[ox][ry][rz] == 1: break |
|||
inc ox |
|||
while oy < n: |
|||
if c[rx][oy][rz] == 1: break |
|||
inc oy |
|||
if not proper and rand(1) == 0: |
|||
inc oy |
|||
while oy < n: |
|||
if c[rx][oy][rz] == 1: break |
|||
inc oy |
|||
while oz < n: |
|||
if c[rx][ry][oz] == 1: break |
|||
inc oz |
|||
if not proper and rand(1) == 0: |
|||
inc oz |
|||
while oz < n: |
|||
if c[rx][ry][oz] == 1: break |
|||
inc oz |
|||
inc c[rx][ry][rz] |
|||
inc c[rx][oy][oz] |
|||
inc c[ox][ry][oz] |
|||
inc c[ox][oy][rz] |
|||
dec c[rx][ry][oz] |
|||
dec c[rx][oy][rz] |
|||
dec c[ox][ry][rz] |
|||
dec c[ox][oy][oz] |
|||
if c[ox][oy][oz] < 0: |
|||
(rx, ry, rz) = (ox, oy, oz) |
|||
proper = false |
|||
else: |
|||
proper = true |
|||
break |
|||
func toMatrix(c: Cube): Matrix = |
|||
let n = c[0].len |
|||
result = newSeqWith(n, newSeq[int](n)) |
|||
for i in 0..<n: |
|||
for j in 0..<n: |
|||
for k in 0..<n: |
|||
if c[i][j][k] != 0: |
|||
result[i][j] = k |
|||
break |
|||
func toReduced(m: Matrix): Matrix = |
|||
let n = m.len |
|||
result = m |
|||
for j in 0..n-2: |
|||
if result[0][j] != j: |
|||
for k in j+1..<n: |
|||
if result[0][k] == j: |
|||
for i in 0..<n: |
|||
swap result[i][j], result[i][k] |
|||
break |
|||
for i in 1..n-2: |
|||
if result[i][0] != i: |
|||
for k in i+1..<n: |
|||
if result[k][0] == i: |
|||
for j in 0..<n: |
|||
swap result[i][j], result[k][j] |
|||
break |
|||
func asArray16(m: Matrix): Array16 = |
|||
var k = 0 |
|||
for i in 0..3: |
|||
for j in 0..3: |
|||
result[k] = m[i][j] |
|||
inc k |
|||
func asArray25(m: Matrix): Array25 = |
|||
var k = 0 |
|||
for i in 0..4: |
|||
for j in 0..4: |
|||
result[k] = m[i][j] |
|||
inc k |
|||
proc printArray16(a: Array16) = |
|||
for i in 0..3: |
|||
for j in 0..3: |
|||
let k = i * 4 + j |
|||
stdout.write &"{a[k]+1:2} " # Back to 1 based. |
|||
echo() |
|||
echo() |
|||
proc printMatrix(m: Matrix) = |
|||
let n = m.len |
|||
for i in 0..<n: |
|||
for j in 0..<n: |
|||
stdout.write &"{m[i][j]+1:2} " # Back to 1 based. |
|||
echo() |
|||
echo() |
|||
randomize() |
|||
# Part 1. |
|||
echo "Part 1: 10_000 latin Squares of order 4 in reduced form:\n" |
|||
const From1: Matrix = @[@[1, 2, 3, 4], @[2, 1, 4, 3], @[3, 4, 1, 2], @[4, 3, 2, 1]] |
|||
var freqs4: CountTable[Array16] |
|||
var c = newCube(From1, 4) |
|||
for _ in 1..10_000: |
|||
c.shuffle() |
|||
let m = c.toMatrix |
|||
let rm = m.toReduced |
|||
let a16 = rm.asArray16 |
|||
freqs4.inc(a16) |
|||
for a, freq in freqs4.pairs: |
|||
printArray16(a) |
|||
echo &"Occurs {freq} times\n" |
|||
# Part 2. |
|||
echo "\nPart 2: 10_000 latin squares of order 5 in reduced form:" |
|||
const From2: Matrix = @[@[1, 2, 3, 4, 5], @[2, 3, 4, 5, 1], @[3, 4, 5, 1, 2], |
|||
@[4, 5, 1, 2, 3], @[5, 1, 2, 3, 4]] |
|||
var freqs5: CountTable[Array25] |
|||
c = newCube(From2, 5) |
|||
for _ in 1..10_000: |
|||
c.shuffle() |
|||
let m = c.toMatrix |
|||
let rm = m.toReduced |
|||
let a25 = rm.asArray25 |
|||
freqs5.inc(a25) |
|||
var count = 0 |
|||
for freq in freqs5.values: |
|||
inc count |
|||
if count > 1: stdout.write ", " |
|||
if (count - 1) mod 8 == 0: echo() |
|||
stdout.write &"{count:2}({freq:3})" |
|||
echo '\n' |
|||
# Part 3. |
|||
echo "\nPart 3: 750 latin squares of order 42, showing the last one:\n" |
|||
var m42: Matrix |
|||
c = newCube(@[], 42) |
|||
for i in 1..750: |
|||
c.shuffle() |
|||
if i == 750: |
|||
m42 = c.toMatrix |
|||
printMatrix(m42) |
|||
# Part 4. |
|||
echo "\nPart 4: 1000 latin squares of order 256:\n" |
|||
let start = cpuTime() |
|||
c = newCube(@[], 256) |
|||
for _ in 1..1000: |
|||
c.shuffle() |
|||
echo &"Generated in {cpuTime() - start:.3f} s."</lang> |
|||
{{out}} |
|||
<pre>Part 1: 10_000 latin Squares of order 4 in reduced form: |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 2 1 |
|||
4 3 1 2 |
|||
Occurs 2469 times |
|||
1 2 3 4 |
|||
2 4 1 3 |
|||
3 1 4 2 |
|||
4 3 2 1 |
|||
Occurs 2430 times |
|||
1 2 3 4 |
|||
2 3 4 1 |
|||
3 4 1 2 |
|||
4 1 2 3 |
|||
Occurs 2561 times |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 1 2 |
|||
4 3 2 1 |
|||
Occurs 2540 times |
|||
Part 2: 10_000 latin squares of order 5 in reduced form: |
|||
1(175), 2(201), 3(209), 4(158), 5(175), 6(190), 7(178), 8(173), |
|||
9(172), 10(179), 11(199), 12(170), 13(167), 14(199), 15(166), 16(164), |
|||
17(180), 18(189), 19(170), 20(183), 21(165), 22(172), 23(199), 24(190), |
|||
25(165), 26(178), 27(178), 28(190), 29(173), 30(187), 31(163), 32(157), |
|||
33(179), 34(190), 35(168), 36(209), 37(185), 38(181), 39(161), 40(180), |
|||
41(162), 42(161), 43(184), 44(157), 45(195), 46(179), 47(181), 48(161), |
|||
49(198), 50(190), 51(176), 52(184), 53(148), 54(209), 55(167), 56(181) |
|||
Part 3: 750 latin squares of order 42, showing the last one: |
|||
31 27 9 29 25 19 40 35 16 34 32 33 10 13 1 36 17 24 39 14 18 26 38 15 21 42 3 6 12 2 41 28 37 7 5 11 23 20 22 4 30 8 |
|||
13 33 39 32 16 26 21 25 3 37 22 11 27 41 42 10 7 2 35 18 14 31 5 17 19 29 20 28 38 9 12 40 8 6 23 30 34 36 24 15 4 1 |
|||
40 7 6 5 21 25 3 4 8 20 1 23 19 35 2 29 24 37 32 39 28 11 9 14 15 26 41 18 36 12 33 16 17 27 38 13 22 34 30 31 42 10 |
|||
17 40 32 42 15 35 18 41 9 25 6 3 30 1 37 34 19 14 4 31 24 28 21 20 38 13 26 27 10 16 36 22 5 12 39 29 33 11 23 8 7 2 |
|||
12 9 29 23 8 22 42 32 33 14 30 31 20 18 10 24 36 13 15 16 3 25 17 26 27 19 7 39 41 21 28 5 2 11 4 1 40 35 37 34 6 38 |
|||
11 2 41 30 3 1 17 22 40 32 5 8 4 14 26 7 10 16 29 9 31 37 25 19 36 27 34 35 24 33 23 21 12 15 20 18 38 39 6 42 13 28 |
|||
24 26 40 4 9 37 36 13 10 28 15 21 22 27 14 20 34 5 6 23 16 38 29 7 8 12 35 41 33 18 19 17 11 1 30 25 2 32 42 3 31 39 |
|||
37 18 4 24 42 38 30 31 20 36 39 2 6 11 41 3 15 33 26 13 9 29 40 32 10 28 23 25 22 34 14 35 1 16 27 12 19 21 8 17 5 7 |
|||
29 39 18 19 37 6 14 1 31 30 2 5 28 8 33 25 23 9 17 21 7 35 20 3 11 16 22 38 15 36 10 32 13 34 26 4 27 40 12 24 41 42 |
|||
4 16 8 10 19 5 6 24 2 12 40 32 15 29 13 41 20 38 36 28 42 39 23 34 17 11 30 14 21 1 27 31 7 3 37 26 35 33 18 22 25 9 |
|||
15 29 12 26 5 9 1 23 32 2 36 16 11 30 21 33 13 3 31 41 8 7 14 37 22 10 39 40 6 20 24 27 42 18 17 28 4 38 19 25 35 34 |
|||
41 22 35 34 28 3 31 17 13 7 23 30 1 4 11 37 29 40 38 10 15 14 24 27 6 21 33 16 2 42 9 8 25 32 18 19 12 5 20 39 36 26 |
|||
25 37 23 33 26 32 22 6 38 13 11 29 5 31 19 27 40 20 14 7 2 12 36 10 34 39 18 24 1 8 4 42 15 30 41 9 3 17 28 35 16 21 |
|||
5 20 21 13 23 15 34 27 25 11 19 12 24 16 17 1 26 28 18 36 30 32 42 22 40 3 37 9 35 10 31 41 4 33 29 38 8 14 2 7 39 6 |
|||
1 12 10 41 14 20 16 33 39 5 27 6 17 23 24 13 38 25 19 15 34 21 28 36 4 30 8 29 32 37 2 9 26 42 7 35 18 22 11 40 3 31 |
|||
6 24 36 7 2 10 28 29 18 41 12 4 25 40 3 17 35 23 11 5 22 42 31 16 9 33 32 21 37 30 38 13 19 8 34 39 26 1 15 20 27 14 |
|||
16 30 25 39 4 33 38 9 15 42 24 36 35 3 31 12 32 18 27 8 41 23 22 13 20 7 21 2 11 6 1 26 10 40 28 14 5 29 34 19 37 17 |
|||
38 3 37 15 11 14 7 8 5 9 41 1 2 24 16 6 12 42 33 27 21 30 32 35 23 25 4 20 18 26 40 36 31 10 22 17 39 28 13 29 34 19 |
|||
26 21 2 1 12 18 25 40 4 16 17 13 33 9 22 30 27 29 3 34 35 36 15 23 24 37 14 19 7 41 5 39 6 38 11 42 10 8 31 28 32 20 |
|||
19 31 20 3 1 42 11 36 30 10 13 7 14 26 5 8 22 35 34 12 25 15 33 38 28 23 17 32 27 39 21 29 41 9 6 2 24 16 4 37 18 40 |
|||
42 10 3 22 35 7 13 5 41 33 34 18 39 28 15 38 14 30 1 37 26 4 16 6 32 40 2 8 31 11 25 12 27 17 19 20 29 24 21 9 23 36 |
|||
10 1 14 6 13 31 23 15 37 18 28 41 12 42 34 4 39 7 22 17 40 5 19 9 29 8 16 33 26 25 32 24 3 20 35 36 11 2 38 27 21 30 |
|||
23 25 11 28 39 24 5 18 35 27 10 15 16 22 4 40 42 21 12 30 38 20 37 2 3 1 31 13 14 17 8 19 29 36 9 34 7 6 26 32 33 41 |
|||
39 36 31 38 20 12 9 37 24 15 7 25 34 21 28 19 41 26 5 22 27 18 8 4 16 17 11 30 23 35 6 1 32 2 13 40 14 42 33 10 29 3 |
|||
14 5 27 40 34 41 19 21 22 31 8 37 42 17 29 23 9 12 20 25 1 3 26 33 13 38 6 4 30 28 39 10 35 24 2 7 15 18 36 16 11 32 |
|||
27 17 34 2 22 11 4 42 12 19 26 9 41 37 36 28 31 15 21 6 32 40 18 30 33 20 29 3 39 38 35 14 23 13 16 8 25 7 10 5 1 24 |
|||
21 14 13 25 27 34 15 20 42 3 4 28 18 5 23 2 30 22 16 26 29 24 41 12 37 6 40 7 9 32 17 38 36 35 10 31 1 19 39 33 8 11 |
|||
28 23 33 9 30 8 12 3 17 6 18 39 38 36 7 42 16 19 24 32 11 1 10 25 35 2 27 31 5 14 13 34 40 37 15 22 20 41 29 21 26 4 |
|||
34 19 42 27 31 21 8 16 7 24 14 35 36 38 20 39 33 41 37 40 13 2 4 1 26 15 12 10 28 23 29 6 9 22 3 32 30 25 5 11 17 18 |
|||
18 11 15 20 36 28 32 26 19 39 42 40 31 25 35 22 8 34 7 38 33 17 6 21 14 9 5 23 4 3 16 30 24 29 1 41 37 13 27 2 10 12 |
|||
33 41 5 35 18 13 10 19 23 8 31 24 32 20 30 15 28 11 42 1 17 6 27 29 7 4 38 26 3 22 37 2 34 39 25 21 36 9 40 12 14 16 |
|||
8 38 26 21 24 30 35 11 14 29 3 10 40 32 6 16 5 31 23 2 39 33 12 42 41 34 1 17 25 4 15 18 20 19 36 37 28 27 7 13 9 22 |
|||
22 6 38 16 33 27 29 28 26 4 21 20 23 34 40 9 1 36 10 11 19 8 35 39 25 31 15 42 17 7 3 37 30 5 14 24 41 12 32 18 2 13 |
|||
20 34 24 12 32 17 37 14 1 22 25 27 26 7 18 21 11 8 9 29 10 13 39 28 2 35 36 5 19 31 42 15 33 4 40 3 16 30 41 6 38 23 |
|||
2 28 16 37 29 40 39 34 6 17 35 38 7 33 32 14 4 27 8 19 20 10 3 41 31 36 24 12 42 5 30 11 18 26 21 15 13 23 9 1 22 25 |
|||
30 42 1 31 41 36 2 39 21 38 9 19 13 6 27 35 37 17 40 3 4 22 11 8 12 18 25 15 34 29 7 23 14 28 24 33 32 10 16 26 20 5 |
|||
36 35 17 8 7 4 41 30 28 26 33 22 29 39 38 31 18 10 2 20 37 19 13 24 42 5 9 34 16 40 11 25 21 14 32 27 6 3 1 23 12 15 |
|||
9 13 7 18 6 2 26 38 27 1 29 34 37 12 25 32 3 4 28 35 23 41 30 40 39 24 10 11 8 15 22 20 16 21 42 5 17 31 14 36 19 33 |
|||
32 15 22 36 38 23 24 10 11 35 20 17 21 19 8 26 2 6 30 42 12 9 34 5 1 14 28 37 29 13 18 7 39 25 33 16 31 4 3 41 40 27 |
|||
7 8 28 17 10 29 20 12 34 21 16 14 3 2 9 5 6 39 25 4 36 27 1 11 18 32 13 22 40 19 26 33 38 41 31 23 42 15 35 30 24 37 |
|||
35 4 19 11 17 16 33 2 36 40 38 26 8 10 39 18 21 32 41 24 5 34 7 31 30 22 42 1 13 27 20 3 28 23 12 6 9 37 25 14 15 29 |
|||
3 32 30 14 40 39 27 7 29 23 37 42 9 15 12 11 25 1 13 33 6 16 2 18 5 41 19 36 20 24 34 4 22 31 8 10 21 26 17 38 28 35 |
|||
Part 4: 1000 latin squares of order 256: |
|||
Generated in 1.306 s.</pre> |
|||
=={{header|Phix}}== |
|||
{{trans|Go}} |
|||
<!--<lang Phix>(phixonline)--> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">shuffleCube</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rz</span> |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">bProper</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">rx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">ry</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">rz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ox</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">oy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">oz</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">ox</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bProper</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">ox</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">oy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bProper</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">oy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">oz</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bProper</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">oz</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">oz</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rz</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ox</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">oy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">oz</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #000000;">bProper</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">bProper</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">toMatrix</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">m</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">toReduced</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">j</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">j</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">mij</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">mik</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mik</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mij</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">mij</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">mkj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mkj</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mij</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">m</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">makeCube</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">orig</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orig</span><span style="color: #0000FF;">==</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">orig</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Part 1: 10,000 latin Squares of order 4 in reduced form:\n\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">orig</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">makeCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orig</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rm</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fk</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">freq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10000</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shuffleCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toMatrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">rm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toReduced</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">fk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_all_keys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v occurs %d times\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nPart 2: 10,000 latin squares of order 5 in reduced form:\n\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">orig</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">}}</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">makeCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orig</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">justclear</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10000</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shuffleCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toMatrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">rm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toReduced</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">fk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_all_keys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">fk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%2d(%3d)"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">-- part 3</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nPart 3: 750 latin squares of order 42, showing the last one:\n\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">makeCube</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">750</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shuffleCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toMatrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #000080;font-style:italic;">-- part 4</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nPART 4: 1000 latin squares of order 256:\n\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">makeCube</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">256</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shuffleCube</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Generated in %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
<!--</lang>--> |
|||
{{out}} |
|||
<pre> |
|||
Part 1: 10,000 latin Squares of order 4 in reduced form: |
|||
{{1,2,3,4},{2,1,4,3},{3,4,1,2},{4,3,2,1}} occurs 2503 times |
|||
{{1,2,3,4},{2,1,4,3},{3,4,2,1},{4,3,1,2}} occurs 2560 times |
|||
{{1,2,3,4},{2,3,4,1},{3,4,1,2},{4,1,2,3}} occurs 2510 times |
|||
{{1,2,3,4},{2,4,1,3},{3,1,4,2},{4,3,2,1}} occurs 2427 times |
|||
Part 2: 10,000 latin squares of order 5 in reduced form: |
|||
1(172) 9(197) 17(228) 25(166) 33(171) 41(224) 49(171) |
|||
2(168) 10(162) 18(216) 26(227) 34(172) 42(155) 50(226) |
|||
3(159) 11(198) 19(206) 27(165) 35(189) 43(190) 51(174) |
|||
4(170) 12(207) 20(159) 28(166) 36(177) 44(171) 52(196) |
|||
5(211) 13(148) 21(172) 29(173) 37(183) 45(189) 53(197) |
|||
6(169) 14(163) 22(128) 30(179) 38(184) 46(138) 54(173) |
|||
7(168) 15(155) 23(146) 31(170) 39(187) 47(170) 55(206) |
|||
8(193) 16(177) 24(146) 32(176) 40(157) 48(183) 56(177) |
|||
Part 3: 750 latin squares of order 42, showing the last one: |
|||
5 29 15 7 25 26 2 35 21 39 8 12 17 31 3 20 23 22 40 34 13 32 27 38 9 6 36 41 11 19 4 42 10 28 33 18 30 16 1 14 37 24 |
|||
34 17 22 12 38 28 20 42 15 10 4 3 30 16 35 23 11 19 31 8 32 1 33 36 24 2 18 39 9 41 40 26 25 27 29 5 7 37 21 13 6 14 |
|||
23 14 41 38 2 36 4 34 29 16 11 10 24 13 26 31 30 12 28 18 7 21 40 42 27 9 37 35 1 3 17 22 20 5 6 33 32 39 25 19 15 8 |
|||
29 21 27 41 3 10 12 23 4 18 39 1 11 6 20 34 2 35 36 37 40 5 14 26 17 42 24 33 32 16 28 8 13 30 15 9 25 19 38 7 31 22 |
|||
8 32 10 17 30 15 18 13 19 6 26 29 34 42 28 40 24 23 33 7 3 4 12 37 38 36 1 21 41 20 16 25 5 11 2 39 14 22 31 35 9 27 |
|||
27 40 39 16 11 23 14 20 6 4 19 28 36 12 31 24 42 10 35 33 17 18 30 3 21 5 38 15 7 1 9 34 8 32 37 13 2 26 29 22 25 41 |
|||
31 39 29 22 20 6 11 17 16 19 41 36 35 33 30 14 4 2 15 24 21 10 25 1 18 12 40 28 5 37 32 27 3 13 42 38 9 34 26 8 7 23 |
|||
11 33 42 28 14 7 6 24 37 26 13 35 9 5 19 18 15 20 25 41 30 17 3 12 22 8 21 27 39 10 34 40 32 36 4 31 23 29 2 38 16 1 |
|||
20 11 7 8 32 31 40 37 42 13 21 22 26 2 12 29 1 27 6 14 19 41 38 17 36 25 4 5 30 15 24 35 16 34 39 3 28 23 9 18 33 10 |
|||
24 9 28 40 33 29 3 7 34 11 16 27 2 30 42 25 21 13 41 10 38 8 39 35 12 26 19 20 23 31 5 32 1 22 14 6 4 15 37 36 17 18 |
|||
2 8 23 37 27 9 38 36 13 24 31 14 29 7 6 42 3 34 18 32 1 20 22 41 25 30 33 16 15 4 11 10 26 39 21 28 17 40 19 5 12 35 |
|||
13 2 26 15 10 40 39 6 33 29 42 34 12 17 11 28 22 32 14 25 24 37 21 5 8 23 30 9 18 7 41 31 4 3 27 19 16 35 20 1 38 36 |
|||
22 23 34 31 28 25 36 38 9 32 30 8 3 11 17 41 26 39 24 6 2 35 13 4 7 21 29 18 14 27 19 37 15 20 16 12 10 33 40 42 1 5 |
|||
36 28 20 11 29 39 22 41 35 7 5 15 31 24 8 19 27 37 1 38 16 13 6 2 32 40 14 25 33 17 21 4 34 23 30 10 18 42 12 9 26 3 |
|||
6 25 8 2 17 33 19 12 1 38 40 39 5 32 18 7 34 30 9 11 15 3 31 23 37 24 27 14 20 28 36 16 21 42 13 29 41 4 35 10 22 26 |
|||
14 24 38 32 12 3 15 2 17 28 36 40 19 26 1 27 29 41 8 5 23 42 20 13 10 34 6 31 16 35 30 7 11 18 22 21 33 25 4 37 39 9 |
|||
39 30 5 20 1 22 9 40 36 27 7 33 37 18 29 38 25 42 4 21 14 31 10 28 26 15 16 8 3 13 35 19 41 2 32 24 12 11 17 23 34 6 |
|||
35 18 17 14 13 41 25 31 2 3 32 24 10 19 22 33 6 1 16 23 9 15 8 39 5 7 11 12 42 34 37 28 38 4 26 20 40 36 27 21 30 29 |
|||
9 19 24 26 42 16 7 30 10 40 29 4 33 8 38 22 14 25 37 28 5 27 41 32 1 13 17 36 34 39 23 11 31 6 35 2 20 21 18 15 3 12 |
|||
12 22 37 1 4 20 32 3 30 25 28 26 6 14 36 11 39 21 38 29 27 24 7 16 15 31 9 34 10 33 13 18 40 35 5 17 19 8 42 41 23 2 |
|||
3 16 31 42 7 17 37 25 23 36 15 18 27 22 5 21 40 9 10 39 4 26 29 6 2 33 41 19 35 8 12 20 28 38 24 32 11 1 34 30 14 13 |
|||
19 41 36 34 21 18 26 29 27 20 14 16 38 40 7 15 32 3 17 4 10 28 35 33 13 22 8 6 25 42 31 23 2 37 9 30 1 12 5 24 11 39 |
|||
25 4 12 29 26 37 16 9 22 30 6 23 40 21 15 35 20 38 19 42 11 2 1 18 3 41 5 10 28 36 33 39 27 24 34 8 31 32 14 17 13 7 |
|||
41 12 14 33 40 35 28 15 7 9 1 5 13 23 27 32 8 17 26 31 42 34 37 19 30 38 20 22 2 6 39 21 36 29 18 16 3 24 11 4 10 25 |
|||
26 20 3 19 16 30 5 14 8 41 10 7 25 15 21 13 38 36 39 22 28 23 17 27 33 37 34 32 4 2 29 12 9 31 1 42 24 18 6 40 35 11 |
|||
10 1 25 36 37 24 8 26 3 12 34 42 18 38 41 16 9 14 32 35 31 30 5 22 39 27 7 4 13 29 6 15 23 19 28 11 21 2 33 20 40 17 |
|||
37 35 40 13 39 8 31 33 38 15 12 32 16 41 34 6 5 11 30 27 20 22 26 14 29 18 28 23 36 21 25 2 7 1 17 4 42 9 10 3 24 19 |
|||
30 34 2 24 35 1 23 10 20 42 22 37 15 39 9 17 12 4 5 26 18 38 16 29 31 3 25 11 21 14 8 41 6 40 19 7 13 27 28 32 36 33 |
|||
16 7 19 21 18 27 29 22 39 35 2 38 28 20 40 9 36 8 12 1 41 33 15 31 11 10 42 24 6 32 26 17 37 14 25 23 5 13 3 34 4 30 |
|||
32 3 11 25 5 12 1 4 18 31 33 19 41 9 37 10 7 24 13 40 6 16 42 21 34 20 26 2 38 22 15 14 35 17 23 36 8 30 39 27 29 28 |
|||
1 13 30 39 36 4 34 32 12 14 17 6 23 27 24 3 41 40 11 20 22 9 28 15 42 16 2 29 31 5 7 33 19 21 10 35 26 38 8 25 18 37 |
|||
18 38 4 23 41 19 35 21 26 33 37 20 42 28 13 5 10 7 3 15 25 39 32 9 14 17 31 40 29 24 1 36 30 8 12 34 27 6 22 11 2 16 |
|||
4 27 21 3 8 42 41 16 40 37 18 2 22 25 32 36 17 5 23 30 29 6 9 34 19 35 15 13 24 11 14 1 12 10 38 26 39 20 7 33 28 31 |
|||
40 26 9 30 6 21 42 19 5 2 3 31 4 35 23 37 28 15 20 13 34 12 11 8 16 14 39 17 22 25 27 38 18 33 7 1 36 10 24 29 41 32 |
|||
28 15 1 4 19 11 24 5 31 8 23 17 21 34 14 26 37 18 7 2 35 29 36 10 6 39 32 30 27 38 3 9 33 16 20 25 22 41 13 12 42 40 |
|||
21 10 35 27 31 2 13 39 28 5 9 41 1 36 4 8 19 29 34 16 33 40 24 25 20 11 22 7 12 18 42 30 14 26 3 37 15 17 23 6 32 38 |
|||
17 42 18 6 23 5 33 1 24 34 35 30 7 37 16 12 31 26 21 19 39 14 4 11 41 32 10 3 40 9 38 13 22 25 36 27 29 28 15 2 8 20 |
|||
42 6 13 35 22 32 10 8 14 21 24 11 39 1 2 4 18 33 27 9 12 25 23 40 28 29 3 26 37 30 20 5 17 41 31 15 38 7 36 16 19 34 |
|||
7 36 16 5 9 34 21 11 32 22 20 25 8 10 33 30 35 31 29 12 26 19 2 24 4 1 13 38 17 23 18 6 39 15 40 14 37 3 41 28 27 42 |
|||
15 37 32 9 24 38 27 28 41 17 25 13 20 29 10 39 33 6 2 36 8 7 18 30 35 4 23 1 19 26 22 3 42 12 11 40 34 14 16 31 5 21 |
|||
33 31 6 18 34 14 17 27 25 1 38 21 32 4 39 2 13 16 42 3 36 11 19 7 23 28 12 37 8 40 10 29 24 9 41 22 35 5 30 26 20 15 |
|||
38 5 33 10 15 13 30 18 11 23 27 9 14 3 25 1 16 28 22 17 37 36 34 20 40 19 35 42 26 12 2 24 29 7 8 41 6 31 32 39 21 4 |
|||
PART 4: 1000 latin squares of order 256: |
|||
Generated in 19.5s |
|||
</pre> |
|||
Unfortunately the last part of this task exposes the relatively poor performance of subscripting in phix. |
|||
=={{header|Raku}}== |
|||
{{trans|Go}} |
|||
<lang perl6># 20210729 Raku programming solution |
|||
sub makeCube(\from, Int \n) { |
|||
my @c = [[[ 0 xx n ] xx n ] xx n ]; |
|||
from.Bool ?? do race for ^n X ^n -> (\i,\j) { @c[i;j; { from[i;j]-1 } ] = 1 } |
|||
!! do race for ^n X ^n -> (\i,\j) { @c[i;j; { (i+j)%n } ] = 1 } |
|||
return @c |
|||
} |
|||
sub shuffleCube(@c is copy) { |
|||
my ($rx, $ry, $rz); my \n = +@c; my Bool \proper = $ = True; |
|||
repeat { ($rx ,$ry, $rz) = (^n).roll: 3 } until @c[$rx;$ry;$rz] == 0; |
|||
loop { |
|||
my ($ox, $oy, $oz); |
|||
for ^n { last if @c[ $ox = $_ ;$ry;$rz] == 1 } |
|||
if !proper and (^3).roll==0 { |
|||
for $ox^…^n { last if @c[ $ox = $_ ;$ry;$rz] == 1 } |
|||
} |
|||
for ^n { last if @c[$rx; $oy = $_ ;$rz] == 1 } |
|||
if !proper and (^3).roll==0 { |
|||
for $oy^…^n { last if @c[$rx; $oy = $_ ;$rz] == 1 } |
|||
} |
|||
for ^n { last if @c[$rx;$ry; $oz = $_ ] == 1 } |
|||
if !proper and (^3).roll==0 { |
|||
for $oz^…^n { last if @c[$rx;$ry; $oz = $_ ] == 1 } |
|||
} |
|||
(@c[$rx;$ry;$rz],@c[$rx;$oy;$oz],@c[$ox;$ry;$oz],@c[$ox;$oy;$rz]) »+=»1; |
|||
(@c[$rx;$ry;$oz],@c[$rx;$oy;$rz],@c[$ox;$ry;$rz],@c[$ox;$oy;$oz]) »-=»1; |
|||
@c[$ox;$oy;$oz] < 0 ?? (($rx,$ry,$rz) = ($ox,$oy,$oz)) !! last ; |
|||
proper = False |
|||
} |
|||
return @c |
|||
} |
|||
sub toMatrix(@c) { |
|||
my \n = +@c; |
|||
my @m = [[0 xx n] xx n]; |
|||
for ^n X ^n -> (\i,\j) { |
|||
for ^n -> \k { if @c[i;j;k] != 0 { @m[i;j] = k and last } } |
|||
} |
|||
return @m |
|||
} |
|||
sub toReduced(@m is copy) { |
|||
my \n = +@m; |
|||
for 0…(n-2) -> \j { |
|||
if ( @m[0;j] != j ) { |
|||
for j^…^n -> \k { |
|||
if ( @m[0;k] == j ) { |
|||
for 0…^n -> \i { (@m[i;j], @m[i;k]) = (@m[i;k], @m[i;j]) } |
|||
last |
|||
} |
|||
} |
|||
} |
|||
} |
|||
for 1…(n-2) -> \i { |
|||
if ( @m[i;0] != i ) { |
|||
for i^…^n -> \k { |
|||
if ( @m[k;0] == i ) { |
|||
for 0…^n -> \j { (@m[i;j], @m[k;j]) = (@m[k;j], @m[i;j]) } |
|||
last |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return @m |
|||
} |
|||
sub printAs1based { say ($_ »+» 1).Str for @_.rotor: @_.elems.sqrt } |
|||
my (%freq, @c, @in); |
|||
say "Part 1: 10,000 latin Squares of order 4 in reduced form:\n"; |
|||
@in = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]]; |
|||
@c = makeCube(@in, 4); |
|||
for ^10_000 { |
|||
@c = shuffleCube @c; |
|||
my @m = toMatrix @c; |
|||
my @rm = toReduced @m; |
|||
%freq{@rm».List.flat.Str}++ |
|||
} |
|||
for %freq.kv -> $k, $v { |
|||
printAs1based $k.split(' '); |
|||
say "\nOccurs $v times.\n" |
|||
} |
|||
say "Part 2: 10,000 latin Squares of order 5 in reduced form:\n"; |
|||
@in = [ [1,2,3,4,5], [2,3,4,5,1], [3,4,5,1,2], [4,5,1,2,3], [5,1,2,3,4] ]; |
|||
%freq = (); |
|||
@c = makeCube(@in, 5); |
|||
for ^10_000 { |
|||
@c = shuffleCube @c; |
|||
my @m = toMatrix @c; |
|||
my @rm = toReduced @m; |
|||
%freq{@rm».List.flat.Str}++ |
|||
} |
|||
for %freq.values.kv -> $i, $j { printf "%2d(%3d)%s", $i+1, $j, ' ' } |
|||
say "\n\nPart 3: 750 latin squares of order 42, showing the last one:\n"; |
|||
@c = makeCube([], 42); # (1..42).pick(*) |
|||
# printAs1based ( toMatrix ( shuffleCube(@c) xx * )[749] )».List.flat ; |
|||
my @m42; |
|||
for ^750 { $_==749 ?? (@m42 = toMatrix(shuffleCube @c)) !! shuffleCube(@c) } |
|||
printAs1based @m42».List.flat ; |
|||
say "\nPart 4: 1000 latin squares of order 256:\n"; |
|||
@c = makeCube([], 256); |
|||
my $snapshot = now; |
|||
race for ^1000 { shuffleCube @c } # ; say "$_\t", now - $snapshot } |
|||
say "Generated in { now - $snapshot } seconds." |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Part 1: 10,000 latin Squares of order 4 in reduced form: |
|||
1 2 3 4 |
|||
2 4 1 3 |
|||
3 1 4 2 |
|||
4 3 2 1 |
|||
Occurs 2564 times. |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 1 2 |
|||
4 3 2 1 |
|||
Occurs 2512 times. |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 2 1 |
|||
4 3 1 2 |
|||
Occurs 2406 times. |
|||
1 2 3 4 |
|||
2 3 4 1 |
|||
3 4 1 2 |
|||
4 1 2 3 |
|||
Occurs 2518 times. |
|||
Part 2: 10,000 latin Squares of order 5 in reduced form: |
|||
1(172) 2(172) 3(179) 4(169) 5(157) 6(189) 7(182) 8(165) 9(170) 10(147) 11(149) 12(198) 13(171) 14(212) 15(167) 16(205) 17(170) 18(199) 19(189) 20(179) 21(196) 22(184) 23(216) 24(218) 25(149) 26(191) 27(163) 28(240) 29(164) 30(182) 31(179) 32(192) 33(173) 34(154) 35(169) 36(145) 37(180) 38(173) 39(168) 40(182) 41(150) 42(150) 43(187) 44(212) 45(190) 46(180) 47(167) 48(163) 49(222) 50(170) 51(181) 52(186) 53(162) 54(171) 55(175) 56(175) |
|||
Part 3: 750 latin squares of order 42, showing the last one: |
|||
3 9 29 34 30 27 19 22 41 36 13 28 42 21 32 10 8 35 16 31 24 15 33 5 37 6 39 26 1 11 7 4 25 38 17 20 2 14 23 40 12 18 |
|||
13 21 32 12 2 14 42 36 8 19 15 30 23 37 34 24 9 4 6 38 40 1 7 10 3 26 17 20 22 16 18 33 35 25 31 28 39 41 29 5 27 11 |
|||
41 37 12 26 23 32 24 5 31 9 14 1 38 36 28 11 39 20 29 42 13 27 35 8 21 22 2 30 34 17 15 25 6 10 18 33 4 40 7 3 19 16 |
|||
15 4 37 42 7 22 27 35 30 23 29 16 19 8 40 34 20 3 5 39 31 41 26 28 36 10 25 14 17 38 9 13 11 33 6 2 24 18 32 21 1 12 |
|||
35 40 14 11 32 42 3 25 26 24 39 31 1 12 29 9 22 18 17 16 38 10 36 33 2 37 30 34 4 28 8 19 21 5 13 23 15 27 6 7 41 20 |
|||
6 33 34 20 19 2 22 10 15 14 26 38 21 41 42 1 17 32 4 8 11 28 29 9 40 16 23 18 31 5 27 35 37 13 25 24 12 7 3 30 36 39 |
|||
40 16 36 2 3 20 17 18 9 1 6 7 34 31 4 39 10 12 22 24 25 35 8 30 26 14 37 33 42 15 11 21 41 23 38 32 29 28 27 19 5 13 |
|||
4 6 17 21 29 15 38 24 33 42 1 9 22 26 7 35 41 10 11 14 37 40 27 39 30 31 8 25 23 36 13 3 32 28 16 12 19 5 20 2 18 34 |
|||
19 27 16 6 11 3 39 34 36 38 10 5 17 24 21 42 14 29 41 22 9 2 37 26 18 30 31 23 20 4 32 12 28 15 33 7 13 1 25 35 8 40 |
|||
10 26 11 9 25 31 23 13 35 2 40 22 6 1 39 5 36 42 37 34 20 18 30 14 28 12 21 38 33 32 16 41 3 27 24 17 7 29 15 8 4 19 |
|||
33 32 5 40 38 28 34 12 10 6 18 13 2 9 11 3 35 24 15 25 19 8 23 17 27 20 14 41 7 26 29 30 1 39 37 36 31 16 42 4 21 22 |
|||
20 17 7 15 28 24 30 26 12 39 4 41 8 3 35 16 37 13 19 23 36 29 11 2 31 18 32 27 14 6 33 34 5 42 1 10 25 22 40 38 9 21 |
|||
2 34 18 35 33 19 5 20 6 26 24 10 37 38 8 28 29 41 3 7 1 17 31 42 14 25 9 39 36 22 23 40 30 32 12 4 16 11 21 13 15 27 |
|||
24 10 31 13 1 35 7 41 34 8 17 29 16 39 23 19 3 26 9 21 14 30 22 4 38 40 11 6 12 42 28 15 33 2 32 27 20 25 36 18 37 5 |
|||
26 18 2 19 21 23 35 16 1 7 3 25 4 17 33 29 12 39 20 41 22 11 42 13 6 28 34 32 10 31 24 27 38 36 14 37 5 8 30 9 40 15 |
|||
12 7 4 37 35 34 18 2 13 20 32 27 5 29 22 40 31 19 21 11 10 26 6 15 16 33 41 28 25 24 14 42 23 1 30 8 17 38 39 36 3 9 |
|||
23 15 28 4 20 7 16 9 11 32 19 17 26 6 12 2 24 1 36 40 30 13 38 25 5 27 33 21 3 39 34 18 14 22 29 42 8 10 37 31 35 41 |
|||
5 36 6 28 18 41 33 1 25 16 38 20 7 10 24 37 42 11 23 26 21 12 2 32 9 4 27 13 30 19 40 39 34 8 22 3 14 35 17 15 29 31 |
|||
36 11 15 25 40 5 2 7 39 34 41 24 35 30 10 31 27 21 42 17 26 38 4 1 19 32 13 37 8 20 12 9 22 16 23 18 3 6 33 29 28 14 |
|||
28 3 1 8 17 12 9 42 38 4 22 32 40 16 30 27 5 7 18 33 41 37 39 23 20 29 19 31 15 21 6 2 10 24 11 34 36 13 35 14 26 25 |
|||
18 13 42 30 12 10 29 19 21 28 31 36 3 4 17 20 40 9 24 37 27 6 34 11 39 8 7 15 35 23 22 32 2 14 5 25 38 26 41 1 16 33 |
|||
37 39 26 5 4 29 41 14 16 31 27 15 20 13 3 38 6 25 2 18 23 24 32 12 11 35 36 1 9 40 21 7 17 34 28 19 10 30 8 33 22 42 |
|||
17 24 38 32 14 39 15 8 22 25 42 11 30 23 13 12 4 36 27 3 5 33 19 7 41 1 16 29 28 10 35 6 20 31 21 40 9 2 18 37 34 26 |
|||
16 25 9 29 39 37 8 27 24 18 20 40 33 15 31 14 21 34 1 6 2 23 5 36 4 13 35 22 32 12 41 38 7 3 19 26 30 17 11 42 10 28 |
|||
7 5 22 41 31 36 11 29 28 15 8 35 32 18 19 30 26 2 38 1 3 14 20 27 25 21 42 4 40 13 17 24 9 37 39 16 34 23 12 6 33 10 |
|||
22 23 13 17 24 9 10 11 29 33 16 12 36 32 37 6 1 40 31 15 18 25 21 3 34 2 28 35 39 41 5 14 27 19 4 30 26 42 38 20 7 8 |
|||
29 1 19 27 5 21 26 23 37 30 7 18 14 25 6 17 33 16 12 32 15 22 13 40 24 39 10 11 38 9 3 8 31 4 20 35 41 36 34 28 42 2 |
|||
9 2 27 39 10 1 36 17 40 22 12 33 29 11 25 13 7 28 34 30 32 3 14 20 8 23 15 5 19 18 38 31 4 21 42 41 37 24 26 16 6 35 |
|||
27 8 40 7 13 33 25 6 4 37 9 2 39 20 16 26 34 15 10 28 12 21 41 38 29 5 24 42 11 35 36 17 18 30 3 14 22 19 1 32 31 23 |
|||
25 35 41 31 9 11 21 40 17 5 2 6 12 34 14 36 23 30 26 29 8 20 18 19 10 42 4 16 37 33 1 22 13 7 27 39 32 15 28 24 38 3 |
|||
30 38 35 10 6 26 12 37 20 13 28 14 25 27 9 15 2 31 40 5 33 39 3 16 22 7 1 19 18 8 42 23 29 41 34 11 21 4 24 17 32 36 |
|||
42 41 20 14 37 18 13 21 27 40 30 23 11 2 15 25 38 22 28 12 29 7 1 31 17 19 26 10 16 3 4 36 8 9 35 6 33 32 5 34 39 24 |
|||
1 22 8 38 42 6 28 30 7 17 23 3 9 14 2 4 13 5 33 10 39 36 24 41 35 34 40 12 29 27 37 11 16 26 15 21 18 31 19 25 20 32 |
|||
21 19 3 24 34 4 32 28 5 29 25 26 27 7 1 18 15 23 13 36 42 16 40 22 33 17 20 2 41 14 30 37 39 6 8 31 35 9 10 12 11 38 |
|||
39 29 21 23 36 38 4 33 32 3 5 34 41 40 20 8 16 27 7 13 28 19 25 35 15 24 18 17 6 30 31 1 26 11 2 9 42 12 22 10 14 37 |
|||
31 14 39 16 15 40 37 32 42 11 36 8 24 22 41 7 18 6 35 19 34 5 17 21 23 9 38 3 26 29 2 28 12 20 10 13 1 33 4 27 25 30 |
|||
34 30 23 18 8 17 6 4 2 27 35 21 15 33 38 32 11 14 39 20 7 9 16 37 42 36 12 40 24 25 26 10 19 29 41 5 28 3 31 22 13 1 |
|||
11 20 24 1 27 8 40 31 14 21 34 19 10 35 26 22 30 33 32 9 4 42 28 18 13 38 3 7 2 37 25 5 15 12 36 29 6 39 16 41 23 17 |
|||
32 42 25 33 26 16 31 38 3 10 11 4 13 28 18 21 19 8 30 35 6 34 15 29 12 41 22 36 5 2 39 20 24 40 9 1 27 37 14 23 17 7 |
|||
8 28 10 3 16 13 14 39 18 41 21 37 31 19 36 33 32 38 25 2 17 4 12 6 7 15 5 24 27 1 20 26 42 35 40 22 23 34 9 11 30 29 |
|||
14 12 30 36 22 25 1 15 23 35 33 39 18 42 5 41 28 37 8 27 16 31 10 24 32 3 6 9 21 34 19 29 40 17 7 38 11 20 13 26 2 4 |
|||
38 31 33 22 41 30 20 3 19 12 37 42 28 5 27 23 25 17 14 4 35 32 9 34 1 11 29 8 13 7 10 16 36 18 26 15 40 21 2 39 24 6 |
|||
Part 4: 1000 latin squares of order 256: |
|||
Generated in 359.960275435 seconds. |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-fmt}} |
|||
{{libheader|Wren-seq}} |
|||
<lang ecmascript>import "random" for Random |
|||
import "/fmt" for Fmt |
|||
import "/seq" for Lst |
|||
var rand = Random.new() |
|||
var toReduced = Fn.new { |m| |
|||
var n = m.count |
|||
var r = List.filled(n, null) |
|||
for (i in 0...n) r[i] = m[i].toList |
|||
for (j in 0...n-1) { |
|||
if (r[0][j] != j) { |
|||
for (k in j+1...n) { |
|||
if (r[0][k] == j) { |
|||
for (i in 0...n) r[i].swap(j, k) |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
for (i in 1...n-1) { |
|||
if (r[i][0] != i) { |
|||
for (k in i+1...n) { |
|||
if (r[k][0] == i) { |
|||
for (j in 0...n) { |
|||
var t = r[i][j] |
|||
r[i][j] = r[k][j] |
|||
r[k][j] = t |
|||
} |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return r |
|||
} |
|||
// 'm' is assumed to be 0 based |
|||
var printMatrix = Fn.new { |m| |
|||
var n = m.count |
|||
for (i in 0...n) { |
|||
for (j in 0...n) Fmt.write("$2d ", m[i][j]+1) // back to 1 based |
|||
System.print() |
|||
} |
|||
System.print() |
|||
} |
|||
// converts 4 x 4 matrix to 'flat' list |
|||
var asList16 = Fn.new { |m| Lst.flatten(m) } |
|||
// converts 5 x 5 matrix to 'flat' list |
|||
var asList25 = Fn.new { |m| Lst.flatten(m) } |
|||
// 'a' is assumed to be 0 based |
|||
var printList16 = Fn.new { |a| |
|||
for (i in 0...4) { |
|||
for (j in 0...4) { |
|||
var k = i*4 + j |
|||
Fmt.write("$2d ", a[k]+1) // back to 1 based |
|||
} |
|||
System.print() |
|||
} |
|||
System.print() |
|||
} |
|||
var shuffleCube = Fn.new { |c| |
|||
var n = c[0].count |
|||
var proper = true |
|||
var rx |
|||
var ry |
|||
var rz |
|||
while (true) { |
|||
rx = rand.int(n) |
|||
ry = rand.int(n) |
|||
rz = rand.int(n) |
|||
if (c[rx][ry][rz] == 0) break |
|||
} |
|||
while (true) { |
|||
var ox = 0 |
|||
var oy = 0 |
|||
var oz = 0 |
|||
while (ox < n) { |
|||
if (c[ox][ry][rz] == 1) break |
|||
ox = ox + 1 |
|||
} |
|||
if (!proper && rand.int(2) == 0) { |
|||
ox = ox + 1 |
|||
while (ox < n) { |
|||
if (c[ox][ry][rz] == 1) break |
|||
ox = ox + 1 |
|||
} |
|||
} |
|||
while (oy < n) { |
|||
if (c[rx][oy][rz] == 1) break |
|||
oy = oy + 1 |
|||
} |
|||
if (!proper && rand.int(2) == 0) { |
|||
oy = oy + 1 |
|||
while (oy < n) { |
|||
if (c[rx][oy][rz] == 1) break |
|||
oy = oy + 1 |
|||
} |
|||
} |
|||
while (oz < n) { |
|||
if (c[rx][ry][oz] == 1) break |
|||
oz = oz + 1 |
|||
} |
|||
if (!proper && rand.int(2) == 0) { |
|||
oz = oz + 1 |
|||
while (oz < n) { |
|||
if (c[rx][ry][oz] == 1) break |
|||
oz = oz + 1 |
|||
} |
|||
} |
|||
c[rx][ry][rz] = c[rx][ry][rz] + 1 |
|||
c[rx][oy][oz] = c[rx][oy][oz] + 1 |
|||
c[ox][ry][oz] = c[ox][ry][oz] + 1 |
|||
c[ox][oy][rz] = c[ox][oy][rz] + 1 |
|||
c[rx][ry][oz] = c[rx][ry][oz] - 1 |
|||
c[rx][oy][rz] = c[rx][oy][rz] - 1 |
|||
c[ox][ry][rz] = c[ox][ry][rz] - 1 |
|||
c[ox][oy][oz] = c[ox][oy][oz] - 1 |
|||
if (c[ox][oy][oz] < 0) { |
|||
rx = ox |
|||
ry = oy |
|||
rz = oz |
|||
proper = false |
|||
} else { |
|||
proper = true |
|||
break |
|||
} |
|||
} |
|||
} |
|||
var toMatrix = Fn.new { |c| |
|||
var n = c[0].count |
|||
var m = List.filled(n, null) |
|||
for (i in 0...n) m[i] = List.filled(n, 0) |
|||
for (i in 0...n) { |
|||
for (j in 0...n) { |
|||
for (k in 0...n) { |
|||
if (c[i][j][k] != 0) { |
|||
m[i][j] = k |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return m |
|||
} |
|||
// 'from' matrix is assumed to be 1 based |
|||
var makeCube = Fn.new { |from, n| |
|||
var c = List.filled(n, null) |
|||
for (i in 0...n) { |
|||
c[i] = List.filled(n, null) |
|||
for (j in 0...n) { |
|||
c[i][j] = List.filled(n, 0) |
|||
var k = (!from) ? (i + j) % n : from[i][j] - 1 |
|||
c[i][j][k] = 1 |
|||
} |
|||
} |
|||
return c |
|||
} |
|||
// part 1 |
|||
System.print("PART 1: 10,000 latin Squares of order 4 in reduced form:\n") |
|||
var from = [ [1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1] ] |
|||
var freqs4 = {} |
|||
var c = makeCube.call(from, 4) |
|||
for (i in 1..10000) { |
|||
shuffleCube.call(c) |
|||
var m = toMatrix.call(c) |
|||
var rm = toReduced.call(m) |
|||
var a16 = asList16.call(rm) |
|||
var a16s = a16.toString // can't use a list as a map key so convert it to string |
|||
freqs4[a16s] = freqs4[a16s] ? freqs4[a16s] + 1 : 1 |
|||
} |
|||
for (me in freqs4) { |
|||
printList16.call(me.key[1..-2].split(", ").map { |n| Num.fromString(n) }.toList) |
|||
Fmt.print("Occurs $d times\n", me.value) |
|||
} |
|||
// part 2 |
|||
System.print("\nPART 2: 10,000 latin squares of order 5 in reduced form:") |
|||
from = [ [1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], |
|||
[4, 5, 1, 2, 3], [5, 1, 2, 3, 4] ] |
|||
var freqs5 = {} |
|||
c = makeCube.call(from, 5) |
|||
for (i in 1..10000) { |
|||
shuffleCube.call(c) |
|||
var m = toMatrix.call(c) |
|||
var rm = toReduced.call(m) |
|||
var a25 = asList25.call(rm) |
|||
var a25s = a25.toString // can't use a list as a map key so convert it to string |
|||
freqs5[a25s] = freqs5[a25s] ? freqs5[a25s] + 1 : 1 |
|||
} |
|||
var count = 0 |
|||
for (freq in freqs5.values) { |
|||
count = count + 1 |
|||
if (count > 1) System.write(", ") |
|||
if ((count-1) % 8 == 0) System.print() |
|||
Fmt.write("$2d($3d)", count, freq) |
|||
} |
|||
System.print("\n") |
|||
// part 3 |
|||
System.print("\nPART 3: 750 latin squares of order 42, showing the last one:\n") |
|||
var m42 |
|||
c = makeCube.call(null, 42) |
|||
for (i in 1..750) { |
|||
shuffleCube.call(c) |
|||
if (i == 750) m42 = toMatrix.call(c) |
|||
} |
|||
printMatrix.call(m42) |
|||
// part 4 |
|||
System.print("\nPART 4: 1,000 latin squares of order 256:\n") |
|||
var start = System.clock |
|||
c = makeCube.call(null, 256) |
|||
for (i in 1..1000) shuffleCube.call(c) |
|||
var elapsed = System.clock - start |
|||
Fmt.print("Generated in $s seconds", elapsed)</lang> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
PART 1: 10,000 latin Squares of order 4 in reduced form: |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 2 1 |
|||
4 3 1 2 |
|||
Occurs 2510 times |
|||
1 2 3 4 |
|||
2 3 4 1 |
|||
3 4 1 2 |
|||
4 1 2 3 |
|||
Occurs 2498 times |
|||
1 2 3 4 |
|||
2 1 4 3 |
|||
3 4 1 2 |
|||
4 3 2 1 |
|||
Occurs 2506 times |
|||
1 2 3 4 |
|||
2 4 1 3 |
|||
3 1 4 2 |
|||
4 3 2 1 |
|||
Occurs 2486 times |
|||
PART 2: 10,000 latin squares of order 5 in reduced form: |
|||
1(187), 2(179), 3(186), 4(176), 5(177), 6(189), 7(193), 8(182), |
|||
9(168), 10(169), 11(147), 12(200), 13(198), 14(169), 15(200), 16(173), |
|||
17(184), 18(179), 19(151), 20(174), 21(160), 22(198), 23(153), 24(184), |
|||
25(170), 26(180), 27(171), 28(180), 29(184), 30(178), 31(197), 32(173), |
|||
33(185), 34(181), 35(200), 36(188), 37(176), 38(196), 39(193), 40(183), |
|||
41(163), 42(163), 43(173), 44(178), 45(177), 46(160), 47(155), 48(165), |
|||
49(181), 50(188), 51(187), 52(182), 53(162), 54(192), 55(183), 56(180) |
|||
PART 3: 750 latin squares of order 42, showing the last one: |
|||
22 31 16 23 19 21 1 17 9 20 15 3 13 25 2 38 34 14 41 5 26 24 11 12 6 27 4 33 39 8 40 30 29 36 42 32 7 10 37 18 28 35 |
|||
7 19 17 16 13 20 32 27 39 34 22 26 5 23 31 4 15 3 29 42 10 12 9 6 38 2 24 1 40 21 36 37 30 35 41 28 25 33 18 8 11 14 |
|||
21 15 11 40 25 18 4 14 38 13 32 8 2 39 37 10 35 24 31 7 1 16 20 42 34 6 9 28 26 30 23 41 36 33 19 27 29 3 5 17 12 22 |
|||
14 32 36 21 7 2 22 41 13 23 27 6 34 12 42 31 37 38 16 19 5 28 17 4 39 9 40 3 11 18 15 1 24 20 29 33 10 35 25 30 26 8 |
|||
9 10 20 37 35 38 40 33 32 12 18 27 19 42 4 1 17 11 7 13 15 14 36 8 25 39 28 6 16 5 2 3 21 23 34 31 41 29 30 26 22 24 |
|||
3 14 5 28 30 6 7 25 10 1 41 36 42 8 40 33 39 32 2 16 27 18 29 15 24 20 17 23 37 11 26 9 38 12 13 19 4 31 22 35 34 21 |
|||
33 28 6 18 22 27 30 38 36 39 14 21 37 26 15 12 10 23 32 3 17 29 24 35 41 16 1 8 20 34 9 13 25 11 5 40 31 7 42 19 4 2 |
|||
23 17 4 36 11 32 29 20 35 5 16 14 10 31 39 9 40 37 42 1 30 15 6 2 12 8 33 13 7 28 18 38 22 21 26 34 19 24 27 25 41 3 |
|||
40 25 13 1 14 24 17 16 42 6 11 28 15 20 8 7 27 35 26 21 41 39 18 31 19 3 34 30 33 9 37 29 12 22 36 5 2 38 4 32 23 10 |
|||
26 4 7 10 41 39 16 19 8 24 40 23 1 2 6 34 14 5 3 15 12 13 21 25 30 29 36 18 38 32 28 42 9 31 35 17 37 27 11 22 20 33 |
|||
27 5 23 17 21 4 6 9 3 7 25 18 32 14 34 19 33 31 28 12 20 38 15 36 2 22 13 35 41 10 11 8 1 39 30 37 24 26 29 42 16 40 |
|||
19 1 21 11 34 22 3 10 26 42 38 12 39 37 14 32 36 9 13 2 7 31 30 24 20 17 29 40 18 41 4 27 23 16 6 35 28 15 33 5 8 25 |
|||
18 3 33 7 27 14 9 8 15 2 34 38 4 6 13 40 41 28 17 31 24 26 37 32 29 19 11 5 10 36 42 35 20 1 22 30 12 16 21 23 25 39 |
|||
4 9 41 5 36 34 39 24 25 11 29 31 40 3 32 18 8 17 21 26 14 27 38 10 35 30 19 15 1 23 7 33 28 2 16 6 22 42 13 20 37 12 |
|||
15 39 25 19 10 3 8 6 11 14 21 4 20 17 41 30 28 12 37 18 32 40 31 26 13 33 7 42 34 16 27 23 5 38 24 36 35 22 1 2 9 29 |
|||
36 8 19 13 16 9 27 11 17 32 1 5 21 41 28 24 3 26 39 33 42 7 10 18 22 25 37 4 6 35 34 20 15 30 40 12 38 14 2 31 29 23 |
|||
31 12 27 3 23 13 25 30 2 9 4 35 22 18 24 26 20 6 36 34 33 11 19 17 14 5 42 29 8 37 16 28 41 10 38 21 1 39 32 7 40 15 |
|||
35 33 28 20 1 37 26 3 21 27 13 40 38 19 25 2 22 4 12 32 8 23 39 29 11 18 6 7 5 17 30 24 16 41 14 42 36 9 15 34 10 31 |
|||
32 13 1 14 9 8 23 34 19 30 35 29 11 33 16 36 2 21 18 37 4 20 12 22 3 38 31 17 42 24 5 25 10 26 39 7 40 28 6 15 27 41 |
|||
24 7 26 30 39 5 41 21 12 22 3 15 36 40 33 6 42 29 10 28 11 34 35 19 4 1 8 37 27 14 38 17 31 25 2 13 32 23 20 16 18 9 |
|||
30 34 38 35 6 25 15 22 40 16 10 32 3 27 11 20 18 33 19 24 39 8 2 5 23 21 26 36 13 1 41 4 17 42 31 29 14 37 12 9 7 28 |
|||
34 21 18 39 8 26 10 32 37 33 12 2 28 4 38 17 24 36 30 25 9 35 40 16 42 7 41 22 3 29 1 11 27 5 15 20 13 19 23 14 31 6 |
|||
37 35 8 25 29 10 38 31 23 21 36 13 30 34 26 27 19 2 4 9 6 42 22 11 16 28 32 20 15 7 24 5 40 14 12 41 18 1 39 3 33 17 |
|||
10 36 40 4 2 7 5 35 1 41 9 20 31 16 29 23 38 34 33 6 28 21 32 39 27 37 22 26 25 15 13 14 8 3 18 11 30 17 24 12 19 42 |
|||
5 29 37 12 31 16 18 13 33 38 39 22 6 30 19 28 11 40 20 27 35 2 42 14 15 10 23 21 9 4 25 7 34 17 32 24 8 36 41 1 3 26 |
|||
29 41 31 9 40 1 20 2 6 28 30 17 23 38 21 42 7 16 11 39 25 4 26 33 18 15 27 14 35 19 22 12 37 24 10 3 5 8 34 13 36 32 |
|||
1 26 32 8 18 17 11 12 29 35 7 42 24 9 20 13 6 22 5 36 31 37 16 41 40 23 10 38 4 33 21 19 2 27 25 14 15 34 3 28 39 30 |
|||
12 11 15 41 42 35 36 29 18 40 33 10 17 21 22 39 5 1 34 30 37 3 7 23 31 24 2 19 28 26 14 32 4 8 20 25 16 6 9 27 38 13 |
|||
38 22 10 33 4 28 24 36 20 18 8 9 35 13 12 15 32 7 23 17 29 5 25 27 1 41 30 16 14 6 31 26 11 19 3 2 34 21 40 39 42 37 |
|||
42 27 39 24 3 11 13 26 41 25 28 37 18 29 35 14 4 19 38 23 2 22 1 20 9 36 5 31 30 12 33 6 32 15 7 8 21 40 16 10 17 34 |
|||
28 20 9 26 38 33 19 1 30 36 42 11 7 15 23 37 25 27 24 35 13 6 41 21 5 4 12 34 32 31 8 22 14 29 17 39 3 18 10 40 2 16 |
|||
13 37 35 42 33 15 31 28 14 3 19 34 16 32 30 25 23 8 27 11 36 9 5 7 10 12 39 24 29 22 6 2 26 40 21 18 20 41 17 4 1 38 |
|||
11 2 34 38 26 23 28 5 24 15 37 30 8 10 7 29 21 41 22 14 40 25 33 13 17 31 16 9 12 42 19 18 3 32 27 4 39 20 36 6 35 1 |
|||
17 42 30 2 28 29 33 37 22 31 20 7 14 5 9 35 12 13 40 38 23 1 27 34 32 26 15 41 19 3 39 10 18 4 11 16 6 25 8 21 24 36 |
|||
2 16 42 6 12 36 14 23 34 37 17 25 9 22 27 41 31 20 15 4 3 10 28 1 7 13 35 11 21 39 29 40 19 18 8 26 33 32 38 24 30 5 |
|||
8 6 14 31 24 30 21 7 5 19 26 16 25 1 36 3 29 42 35 10 18 17 4 40 37 34 38 32 22 2 12 39 33 13 23 9 27 11 28 41 15 20 |
|||
20 40 12 29 37 42 34 4 27 26 2 33 41 7 10 22 1 15 25 8 38 36 3 30 21 32 18 39 24 13 35 16 6 9 28 23 17 5 31 11 14 19 |
|||
16 18 24 22 20 41 42 40 28 8 23 1 12 11 3 21 26 39 6 29 34 32 14 37 33 35 25 10 2 38 17 31 13 7 4 15 9 30 19 36 5 27 |
|||
41 30 2 34 5 12 37 15 16 17 24 39 33 36 18 8 13 10 14 20 22 19 23 38 26 40 3 25 31 27 32 21 35 28 9 1 42 4 7 29 6 11 |
|||
39 23 3 15 32 40 2 18 7 29 31 24 27 35 5 16 9 30 1 22 19 41 8 28 36 14 20 12 17 25 10 34 42 6 33 38 11 13 26 37 21 4 |
|||
25 24 29 27 17 31 35 42 4 10 6 19 26 28 1 5 30 18 9 41 16 33 13 3 8 11 21 2 36 40 20 15 39 34 37 22 23 12 14 38 32 7 |
|||
6 38 22 32 15 19 12 39 31 4 5 41 29 24 17 11 16 25 8 40 21 30 34 9 28 42 14 27 23 20 3 36 7 37 1 10 26 2 35 33 13 18 |
|||
PART 4: 1,000 latin squares of order 256: |
|||
Generated in 10.828862 seconds |
|||
</pre> |