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

From Rosetta Code
Content added Content deleted
(→‎{{header|Go}}: Added a second much quicker but less uniform version.)
(→‎{{header|Go}}: First version now far quicker thanks to advice by Nigel Galloway and second version removed as no longer necessary.)
Line 128: Line 128:


=={{header|Go}}==
=={{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.
===Parts 1, 2 and (a small part of) 3===
The J & M implementation is based on the C code [https://brainwagon.org/2016/05/17/code-for-generating-a-random-latin-square/ here]. Although this produces satisfactory results for Parts 1 and 2, it is glacial for Part 3 and could only generate 5 order 42 Latin squares in around 22 seconds. Optimizing the code somewhat gets this down to about 14 seconds which suggests that the full 750 could be generated in about 35 minutes though Part 4 is still well out of reach.


All timings are for my Celeron @1.6 GHz and will therefore be much faster on a more modern machine though probably still far too slow for the later Parts.
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
<lang go>package main


Line 233: Line 232:
n := len(c[0])
n := len(c[0])
proper := true
proper := true
iters := n * n * n
var rx, ry, rz int
for i := 0; i < iters; i++ {
for {
var rx, ry, rz int
rx = rand.Intn(n)
for {
ry = rand.Intn(n)
rx = rand.Intn(n)
rz = rand.Intn(n)
ry = rand.Intn(n)
if c[rx][ry][rz] == 0 {
rz = rand.Intn(n)
break
if c[rx][ry][rz] == 0 {
}
}
for {
var ox, oy, oz int
for ; ox < n; ox++ {
if c[ox][ry][rz] == 1 {
break
break
}
}
}
}
for {
if !proper && rand.Intn(2) == 0 {
var ox, oy, oz int
for ox++; ox < n; ox++ {
for ; ox < n; ox++ {
if c[ox][ry][rz] == 1 {
if c[ox][ry][rz] == 1 {
break
break
}
}
}
}
}
if !proper && rand.Intn(2) == 0 {
for ox++; ox < n; ox++ {
if c[ox][ry][rz] == 1 {
break
}
}
}


for ; oy < n; oy++ {
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 {
if c[rx][oy][rz] == 1 {
break
break
}
}
}
}
}
if !proper && rand.Intn(2) == 0 {

for oy++; oy < n; oy++ {
if c[rx][oy][rz] == 1 {
for ; oz < n; oz++ {
break
if c[rx][ry][oz] == 1 {
}
break
}
}
}
}

for ; oz < n; oz++ {
if !proper && rand.Intn(2) == 0 {
for oz++; oz < n; oz++ {
if c[rx][ry][oz] == 1 {
if c[rx][ry][oz] == 1 {
break
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][ry][rz]++
c[rx][oy][oz]++
c[rx][oy][oz]++
c[ox][ry][oz]++
c[ox][ry][oz]++
c[ox][oy][rz]++
c[ox][oy][rz]++


c[rx][ry][oz]--
c[rx][ry][oz]--
c[rx][oy][rz]--
c[rx][oy][rz]--
c[ox][ry][rz]--
c[ox][ry][rz]--
c[ox][oy][oz]--
c[ox][oy][oz]--


if c[ox][oy][oz] < 0 {
if c[ox][oy][oz] < 0 {
rx, ry, rz = ox, oy, oz
rx, ry, rz = ox, oy, oz
proper = false
proper = false
} else {
} else {
proper = true
proper = true
break
break
}
}
}
}
}
Line 391: Line 387:


// part 3
// part 3
fmt.Println("\nPART 3: 5 latin squares of order 42, showing the last one:\n")
fmt.Println("\nPART 3: 750 latin squares of order 42, showing the last one:\n")
start := time.Now()
var m42 matrix
var m42 matrix
c = makeCube(nil, 42)
c = makeCube(nil, 42)
for i := 1; i <= 5; i++ {
for i := 1; i <= 750; i++ {
shuffleCube(c)
shuffleCube(c)
m42 = toMatrix(c)
if i == 750 {
m42 = toMatrix(c)
}
}
}
elapsed := time.Since(start)
printMatrix(m42)
printMatrix(m42)

fmt.Printf("Took %s\n", elapsed)
// 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>
}</lang>


Line 408: Line 413:
<pre>
<pre>
PART 1: 10,000 latin Squares of order 4 in reduced form:
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 2509 times

1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1

Occurs 2571 times

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Occurs 2446 times


1 2 3 4
1 2 3 4
Line 435: Line 419:
4 3 1 2
4 3 1 2


Occurs 2474 times
Occurs 2550 times


PART 2: 10,000 latin squares of order 5 in reduced form:

1(183), 2(189), 3(162), 4(188), 5(191), 6(171), 7(154), 8(212),
9(169), 10(177), 11(198), 12(174), 13(181), 14(177), 15(189), 16(162),
17(202), 18(188), 19(167), 20(194), 21(167), 22(158), 23(157), 24(154),
25(183), 26(160), 27(192), 28(186), 29(187), 30(171), 31(159), 32(182),
33(156), 34(198), 35(165), 36(170), 37(166), 38(163), 39(182), 40(161),
41(198), 42(188), 43(176), 44(190), 45(217), 46(178), 47(153), 48(199),
49(178), 50(158), 51(192), 52(205), 53(177), 54(184), 55(183), 56(179)


PART 3: 5 latin squares of order 42, showing the last one:

18 21 11 26 2 8 25 39 38 24 3 19 33 37 5 16 30 4 9 40 32 31 36 22 1 42 7 12 27 35 23 13 17 14 15 10 41 29 20 34 6 28
41 30 9 40 37 11 16 14 2 32 42 33 7 5 12 1 18 34 23 19 26 22 35 25 36 24 4 21 28 6 39 15 20 8 27 38 17 3 13 10 31 29
8 29 34 2 19 3 6 4 23 30 36 38 11 39 26 28 10 7 22 24 42 25 16 32 17 14 5 9 33 41 31 40 18 27 13 1 37 21 35 12 20 15
30 15 8 18 28 7 31 2 16 10 38 4 26 29 17 25 9 35 14 20 41 33 39 11 24 5 3 36 21 27 1 23 37 40 42 22 12 19 34 32 13 6
39 41 20 17 27 19 24 38 34 16 6 32 29 13 28 3 25 8 1 11 31 12 10 33 23 21 37 2 40 5 18 22 14 7 26 35 9 42 15 36 4 30
2 1 23 15 26 35 36 29 13 6 27 31 12 30 40 7 39 19 3 34 21 17 42 20 14 38 9 8 41 11 22 33 4 5 24 28 18 37 25 16 32 10
28 31 7 10 40 24 30 11 35 23 33 17 32 18 22 12 42 25 13 15 8 21 9 16 41 3 27 5 38 36 6 20 19 4 1 29 39 34 26 2 14 37
6 26 3 12 13 40 38 30 33 17 20 29 28 9 34 15 24 32 39 14 11 8 25 21 19 1 35 23 5 16 2 41 36 31 7 37 22 4 10 18 42 27
19 5 26 31 36 12 33 6 4 1 21 27 38 17 7 20 34 14 32 22 3 2 8 10 9 35 16 18 39 15 37 42 41 29 28 24 30 13 11 40 23 25
5 22 36 11 29 42 41 17 39 40 4 9 8 25 1 21 3 24 7 23 35 13 27 26 38 12 33 31 14 28 15 18 2 34 32 20 10 30 6 19 37 16
33 36 32 28 11 17 14 9 25 21 23 7 15 3 24 2 4 22 31 26 30 10 34 41 27 19 38 29 1 40 20 35 13 18 6 39 8 16 42 37 12 5
16 25 10 3 23 26 20 32 17 5 31 40 36 1 4 27 14 39 11 28 12 9 24 19 33 8 42 22 2 30 38 21 34 15 29 7 35 6 37 13 41 18
40 28 17 16 39 25 37 41 22 15 30 8 42 20 11 19 35 26 10 29 7 5 13 18 21 6 36 32 12 24 27 4 33 23 9 3 38 2 31 14 1 34
25 37 1 29 7 28 9 19 26 22 13 41 21 2 6 39 12 3 16 27 17 42 14 36 18 15 30 4 11 20 35 8 24 32 10 34 40 31 33 38 5 23
37 34 18 33 35 38 27 23 41 8 28 10 39 40 31 5 11 1 30 9 24 29 3 7 25 32 6 16 26 13 14 19 42 17 2 15 20 36 12 4 22 21
15 3 37 35 38 21 32 42 36 34 16 18 30 33 19 41 20 5 27 25 13 7 28 1 2 11 24 14 6 17 8 10 40 22 39 12 4 9 23 29 26 31
10 35 13 1 42 6 34 20 9 4 5 14 22 23 38 30 7 11 28 21 27 32 2 15 8 39 29 40 37 26 25 24 12 19 41 18 3 17 16 31 36 33
23 33 39 20 25 9 40 34 30 35 15 42 37 14 3 18 21 2 8 12 36 4 17 5 26 31 10 6 13 1 24 16 22 41 38 11 27 28 19 7 29 32
12 27 16 39 30 4 18 15 14 20 35 1 40 8 9 23 38 36 41 2 34 11 19 6 29 17 22 10 25 37 13 28 31 33 5 42 26 7 32 21 24 3
24 9 38 42 41 34 21 36 18 25 8 16 1 12 10 17 27 37 19 32 20 26 33 13 30 4 28 15 29 39 7 31 5 3 35 23 6 22 14 11 40 2
22 39 19 13 9 23 11 7 20 28 10 5 18 36 41 14 40 27 15 16 38 6 31 34 3 2 17 37 35 33 30 12 29 42 25 4 24 32 21 1 8 26
9 40 27 36 10 20 4 1 42 14 2 13 5 41 37 8 15 18 25 7 19 23 6 35 32 29 26 3 22 12 33 30 28 21 16 31 34 11 17 24 38 39
3 42 25 24 8 5 17 22 1 13 14 36 20 35 2 31 26 29 37 33 18 34 11 30 15 40 19 27 7 10 28 32 9 16 4 6 23 12 38 39 21 41
20 16 29 9 1 2 15 5 31 18 19 37 35 26 32 24 6 30 4 42 22 28 23 3 12 13 25 39 36 34 41 14 10 38 40 21 11 27 7 8 33 17
17 32 28 41 6 30 8 37 21 29 24 34 10 38 18 35 19 16 33 31 25 14 15 40 4 9 12 42 23 7 3 5 27 26 22 2 36 1 39 20 11 13
11 4 5 22 16 15 12 25 40 33 1 39 31 7 23 42 36 10 29 6 14 27 30 38 28 37 13 26 34 9 32 3 35 20 21 41 2 24 18 17 19 8
32 7 35 6 22 13 28 16 37 26 17 3 24 15 25 40 33 9 18 5 10 20 12 4 11 41 14 30 8 21 29 34 38 2 31 36 1 23 27 42 39 19
34 18 22 21 32 14 39 26 7 38 12 24 27 10 36 13 29 15 17 30 33 1 41 37 42 25 20 11 19 23 4 2 16 6 8 5 31 40 3 28 35 9
31 23 40 27 3 41 29 24 11 39 25 21 34 32 15 38 13 6 12 10 9 16 37 8 20 28 1 17 4 18 5 26 7 36 33 19 42 35 2 22 30 14
38 8 33 19 15 10 23 12 32 42 7 2 6 4 14 36 17 31 35 18 37 39 1 29 16 22 21 13 24 25 34 27 3 11 20 9 5 41 30 26 28 40
13 20 42 4 17 32 3 28 15 2 37 22 14 16 29 11 1 21 26 39 6 24 5 31 40 27 34 41 9 38 12 7 30 25 19 8 33 10 36 23 18 35
27 2 30 37 31 22 35 8 19 36 41 12 4 34 39 29 16 23 38 13 28 40 21 24 6 26 15 7 20 42 9 17 25 10 18 14 32 5 1 33 3 11
1 17 24 32 20 36 10 31 29 37 22 28 23 11 27 34 41 33 42 38 4 3 40 2 5 7 39 35 15 19 26 9 6 13 14 30 21 18 8 25 16 12
26 14 15 30 24 18 42 10 8 7 32 25 3 19 33 6 31 28 40 36 5 35 4 23 34 20 2 38 16 29 21 1 11 12 37 27 13 39 41 9 17 22
35 38 41 23 4 39 26 13 28 3 18 20 19 6 16 32 2 12 5 8 1 37 22 27 10 34 40 33 17 31 42 29 21 30 11 25 7 14 24 15 9 36
29 24 6 7 21 16 22 33 12 31 11 23 13 27 8 26 28 38 34 35 40 41 18 14 39 10 32 1 3 4 19 37 15 9 36 17 25 20 5 30 2 42
36 12 31 14 18 29 5 40 10 27 39 30 17 24 21 22 37 13 6 3 15 38 32 9 7 23 8 28 42 2 16 11 1 35 34 33 19 26 4 41 25 20
14 11 4 25 34 1 7 27 5 19 9 26 41 42 30 33 22 17 21 37 2 15 20 12 35 16 18 24 31 3 40 36 32 39 23 13 29 8 28 6 10 38
4 19 14 5 33 37 2 35 24 41 29 15 9 21 20 10 23 42 36 17 39 18 38 28 13 30 31 34 32 8 11 6 26 1 12 40 16 25 22 3 27 7
7 6 21 38 14 33 13 18 3 12 40 11 2 22 35 37 5 41 20 4 29 19 26 42 31 36 23 25 10 32 17 39 8 24 30 16 28 15 9 27 34 1
21 13 2 8 12 27 19 3 6 11 34 35 25 31 42 9 32 40 24 1 16 36 7 39 37 18 41 20 30 22 10 38 23 28 17 26 14 33 29 5 15 4
42 10 12 34 5 31 1 21 27 9 26 6 16 28 13 4 8 20 2 41 23 30 29 17 22 33 11 19 18 14 36 25 39 37 3 32 15 38 40 35 7 24

Took 13.714977269s
</pre>

===Parts 1, 2, 3 and (a small part of) 4===
The J & M implementation this time is based on the optimized Go code [https://blog.paulhankin.net/latinsquares/ here] which is more than 100 times quicker than before. The full 750 order 42 latin squares are now generated in around 17 seconds. Even Part 4 is now within reach with 10 order 256 latin squares being produced in 70 seconds suggesting the full 1,000 could be produced in under 2 hours.

However, this is at the expense of Part 1 now producing non-uniform results and Part 2 (though more uniform) being less than ideal. This doesn't matter so much for Parts 3 and 4 where the number of possibilities is astronomic in any case though it is still, of course, a concern.
<lang go>package main

import (
"fmt"
"math/rand"
"time"
)

type (
vector []int
matrix []vector
)

func rand2(a, b int) (int, int) {
if rand.Intn(2) == 0 {
return a, b
}
return b, a
}

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 shuffleMatrix(xy matrix) {
n := len(xy)
xz := make(matrix, n)
yz := make(matrix, n)
for i := 0; i < n; i++ {
yz[i] = make([]int, n)
xz[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
k := xy[i][j]
xz[i][k] = j
yz[j][k] = i
}
}

var mxy, mxz, myz int
var m [3]int
proper := true
minIter := n * n * n
for iter := 0; iter < minIter || !proper; iter++ {
var i, j, k, i2, j2, k2 int
var i2_, j2_, k2_ int

if proper {
// Pick a random 0 in the array
i, j, k = rand.Intn(n), rand.Intn(n), rand.Intn(n)
for xy[i][j] == k {
i, j, k = rand.Intn(n), rand.Intn(n), rand.Intn(n)
}
// find i2 such that [i2, j, k] is 1. same for j2, k2
i2 = yz[j][k]
j2 = xz[i][k]
k2 = xy[i][j]
i2_, j2_, k2_ = i, j, k
} else {
i, j, k = m[0], m[1], m[2]
// find one such that [i2, j, k] is 1, same for j2, k2.
// each is either the value stored in the corresponding
// slice, or one of our three temporary "extra" 1s.
// That's because (i, j, k) is -1.
i2, i2_ = rand2(yz[j][k], myz)
j2, j2_ = rand2(xz[i][k], mxz)
k2, k2_ = rand2(xy[i][j], mxy)
}

proper = xy[i2][j2] == k2
if !proper {
m = [3]int{i2, j2, k2}
mxy = xy[i2][j2]
myz = yz[j2][k2]
mxz = xz[i2][k2]
}

xy[i][j] = k2_
xy[i][j2] = k2
xy[i2][j] = k2
xy[i2][j2] = k

yz[j][k] = i2_
yz[j][k2] = i2
yz[j2][k] = i2
yz[j2][k2] = i

xz[i][k] = j2_
xz[i][k2] = j2
xz[i2][k] = j2
xz[i2][k2] = j
}
}

// 'from' matrix is assumed to be 1 based
func makeMatrix(from matrix, n int) matrix {
m := make(matrix, n)
for i := 0; i < n; i++ {
m[i] = make(vector, n)
for j := 0; j < n; j++ {
var k int
if from == nil {
k = (i + j) % n
} else {
k = from[i][j] - 1
}
m[i][j] = k
}
}
return m
}

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)
m := makeMatrix(from, 4)
for i := 1; i <= 10000; i++ {
shuffleMatrix(m)
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)
m = makeMatrix(from, 5)
for i := 1; i <= 10000; i++ {
shuffleMatrix(m)
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")
start := time.Now()
m = makeMatrix(nil, 42)
for i := 1; i <= 750; i++ {
shuffleMatrix(m)
}
elapsed := time.Since(start)
printMatrix(m)
fmt.Printf("Took %s\n", elapsed)

// part 4
fmt.Println("\nPART 5: 10 latin squares of order 256:\n")
start = time.Now()
m = makeMatrix(nil, 256)
for i := 1; i <= 10; i++ {
shuffleMatrix(m)
}
elapsed = time.Since(start)
fmt.Printf("Took %s\n", elapsed)
}</lang>

{{out}}
Sample run:
<pre>
PART 1: 10,000 latin Squares of order 4 in reduced form:


1 2 3 4
1 2 3 4
Line 770: Line 426:
4 3 2 1
4 3 2 1


Occurs 2976 times
Occurs 2430 times


1 2 3 4
1 2 3 4
2 1 4 3
2 1 4 3
3 4 2 1
3 4 1 2
4 3 1 2
4 3 2 1


Occurs 3090 times
Occurs 2494 times


1 2 3 4
1 2 3 4
Line 784: Line 440:
4 1 2 3
4 1 2 3


Occurs 3053 times
Occurs 2526 times

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Occurs 881 times




PART 2: 10,000 latin squares of order 5 in reduced form:
PART 2: 10,000 latin squares of order 5 in reduced form:


1(237), 2(170), 3(160), 4(181), 5(174), 6(211), 7(191), 8(153),
1(165), 2(173), 3(167), 4(204), 5(173), 6(165), 7(215), 8(218),
9(162), 10(153), 11(175), 12(184), 13(169), 14(162), 15(174), 16(168),
9(168), 10(157), 11(205), 12(152), 13(187), 14(173), 15(215), 16(185),
17(177), 18(178), 19(185), 20(169), 21(234), 22(186), 23(173), 24(180),
17(179), 18(176), 19(179), 20(160), 21(150), 22(166), 23(191), 24(181),
25(184), 26(166), 27(176), 28(172), 29(154), 30(145), 31(148), 32(165),
25(179), 26(192), 27(187), 28(186), 29(176), 30(196), 31(141), 32(187),
33(166), 34(175), 35(154), 36(176), 37(166), 38(162), 39(180), 40(206),
33(165), 34(189), 35(147), 36(175), 37(172), 38(162), 39(180), 40(172),
41(191), 42(236), 43(179), 44(223), 45(165), 46(148), 47(181), 48(173),
41(189), 42(159), 43(197), 44(158), 45(178), 46(179), 47(193), 48(175),
49(164), 50(226), 51(175), 52(177), 53(239), 54(169), 55(171), 56(182)
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:
PART 3: 750 latin squares of order 42, showing the last one:


8 23 13 39 42 41 3 15 26 9 18 11 30 19 7 10 22 5 29 34 21 12 17 20 36 2 28 4 40 33 31 35 37 14 1 27 38 25 24 6 32 16
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
36 16 23 30 10 34 31 6 5 11 39 27 14 37 26 25 12 38 17 1 4 20 35 2 3 18 21 24 15 7 13 32 40 8 19 42 9 28 41 33 22 29
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
23 10 1 37 24 18 34 35 16 21 11 33 5 12 40 17 36 27 6 42 25 39 20 9 29 15 14 7 8 26 3 41 22 32 2 19 31 13 30 4 28 38
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
4 9 35 20 25 10 13 32 27 39 14 15 12 42 34 19 29 6 23 30 18 36 1 3 7 38 24 28 21 8 16 40 33 41 31 26 5 2 22 11 37 17
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
1 13 40 14 26 5 11 21 28 29 27 36 4 25 6 22 15 18 30 35 9 10 39 33 19 16 3 20 7 34 2 12 23 31 37 17 8 41 32 24 38 42
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 38 34 21 15 42 40 19 29 4 2 35 24 28 10 27 37 17 26 9 3 31 13 11 14 41 23 30 39 36 5 6 25 1 16 20 7 8 18 32 12 22
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
13 14 29 16 37 30 25 41 39 31 38 5 40 2 22 34 23 32 28 27 7 24 9 35 18 1 8 3 33 12 10 26 19 17 4 6 21 15 42 20 36 11
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
5 41 17 24 28 7 14 36 1 13 8 16 9 18 42 26 20 3 37 2 32 29 11 34 38 19 22 40 31 6 25 27 4 30 12 15 10 23 39 35 33 21
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
11 22 28 27 35 15 19 8 41 24 33 31 20 26 36 23 7 39 34 18 13 1 38 25 5 4 32 17 3 40 42 30 9 37 10 14 16 21 29 2 6 12
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
38 20 24 2 23 3 27 10 18 41 32 17 22 7 31 30 28 36 35 19 6 42 4 13 40 34 39 25 12 21 9 14 1 15 5 16 37 26 33 29 11 8
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
42 37 15 31 7 20 18 9 4 28 10 3 16 6 13 8 5 33 40 12 24 11 27 41 1 23 2 38 32 14 21 17 35 39 25 29 30 19 26 22 34 36
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
41 18 22 17 38 40 29 30 10 33 7 25 21 34 9 12 11 4 3 24 14 27 2 1 35 42 26 16 19 23 39 8 31 13 28 32 36 20 37 15 5 6
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
17 33 18 10 21 11 4 27 6 23 41 28 37 15 19 13 40 7 16 39 29 32 30 12 8 26 1 42 38 2 22 36 34 9 35 31 3 5 20 14 25 24
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
28 17 2 8 33 27 5 34 22 15 23 13 1 35 41 29 42 19 12 6 16 38 10 39 20 14 40 11 36 31 26 4 21 18 32 25 24 9 3 7 30 37
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
12 39 36 35 8 21 28 13 2 6 22 23 27 3 5 11 31 29 15 14 17 33 32 30 42 24 34 9 26 25 19 37 41 4 40 10 1 38 7 16 20 18
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
16 25 39 3 40 6 8 2 20 1 12 10 35 30 17 41 13 37 32 26 19 15 34 7 31 22 4 33 29 18 24 23 42 27 11 5 28 14 38 36 21 9
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
25 40 20 38 29 14 24 26 11 42 35 37 39 13 2 7 3 23 31 10 5 16 21 17 6 9 12 27 41 15 18 19 28 33 22 1 4 34 36 30 8 32
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
24 15 25 33 11 1 35 3 37 8 20 34 26 14 28 2 30 22 42 29 31 19 41 32 23 40 38 6 16 10 17 9 39 21 18 4 12 36 13 5 7 27
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
14 29 5 42 31 37 21 23 9 27 17 39 7 32 8 35 41 1 11 25 22 30 36 16 2 33 6 13 18 19 20 15 24 40 26 38 34 12 4 10 3 28
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
40 26 31 32 1 19 2 7 35 3 9 18 6 23 15 28 38 16 21 37 30 14 8 29 4 36 42 5 27 22 11 20 13 12 33 24 41 10 34 17 39 25
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
21 2 8 29 20 9 22 18 38 14 16 1 33 27 37 5 26 12 24 3 40 28 19 15 32 25 17 31 6 41 4 13 11 36 39 34 23 30 35 42 10 7
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
10 21 6 36 2 39 37 42 8 20 15 24 38 41 1 32 4 25 27 40 33 23 16 31 9 11 19 18 34 13 7 5 17 22 30 12 14 35 28 26 29 3
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
7 11 38 28 19 32 36 14 31 5 34 26 3 22 33 40 17 2 8 16 12 4 24 10 21 13 18 29 23 30 27 25 20 6 41 37 15 42 9 1 35 39
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
30 19 4 34 12 22 10 33 7 2 3 9 31 5 16 20 8 11 1 28 41 25 6 37 13 35 36 32 42 29 38 18 27 24 15 39 26 17 21 40 14 23
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
2 35 12 1 27 26 32 22 13 7 25 4 29 17 39 9 18 31 36 21 15 8 23 38 10 3 30 37 5 20 34 28 6 42 24 11 33 16 14 19 40 41
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
19 31 16 7 41 28 38 11 24 40 42 12 36 8 27 37 39 35 4 13 26 9 5 23 33 6 20 1 2 32 30 21 29 34 14 3 17 22 15 25 18 10
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
9 12 11 18 13 25 30 28 3 32 40 20 23 33 24 36 19 26 38 5 39 41 7 8 22 37 15 14 1 42 6 29 16 10 34 21 35 31 2 27 17 4
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
26 28 10 9 4 33 6 17 23 34 5 38 25 36 29 31 35 21 22 41 42 2 15 40 30 20 16 39 24 3 12 11 14 19 13 7 18 32 8 37 27 1
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
31 32 37 11 30 29 16 20 21 25 24 40 17 38 35 4 9 15 33 36 10 6 12 28 26 27 13 19 22 1 14 7 8 5 3 41 39 18 23 34 42 2
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
3 36 9 15 17 4 39 31 40 22 1 7 2 21 38 6 16 13 5 33 20 34 28 14 41 32 35 23 10 24 8 42 12 29 27 30 25 37 11 18 19 26
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
18 8 27 22 16 38 1 29 32 26 30 42 28 11 14 21 6 34 13 15 35 5 33 19 24 39 37 41 17 4 23 10 7 20 9 36 40 3 25 12 2 31
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
34 24 30 4 5 31 7 12 36 38 19 6 42 1 32 33 14 41 10 17 11 26 37 22 16 29 25 8 20 39 35 2 18 23 21 28 13 40 27 3 9 15
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 41 5 18 12 20 25 14 35 21 32 13 16 4 15 10 24 39 11 27 22 3 36 28 31 33 34 9 17 29 38 30 26 42 40 2 1 6 8 23 19
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
27 4 26 41 14 24 17 37 34 30 36 8 32 40 12 42 2 10 18 38 28 13 31 6 15 7 29 21 25 9 33 1 3 11 20 22 19 39 5 23 16 35
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
39 27 42 25 36 8 9 4 15 18 13 14 34 20 30 16 21 28 7 22 2 40 29 26 37 17 41 12 11 5 32 31 10 3 23 35 6 24 19 38 1 33
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
29 5 33 12 3 35 23 40 42 19 6 2 15 39 25 18 32 30 41 4 37 21 14 24 27 28 11 10 13 16 1 22 36 38 17 8 20 7 31 9 26 34
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
22 30 32 40 6 23 33 16 12 17 37 21 19 29 18 3 34 9 14 7 36 35 26 42 25 10 5 15 4 38 41 24 2 28 8 13 27 11 1 39 31 20
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
20 42 3 19 9 17 12 38 30 37 28 29 41 24 11 39 1 8 2 32 23 7 40 21 34 5 27 26 14 35 36 16 15 25 6 18 22 33 10 31 4 13
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
35 3 7 6 32 16 15 5 19 12 29 41 8 31 20 14 33 42 25 23 1 18 22 27 39 21 10 36 30 28 37 34 26 2 38 9 11 4 17 13 24 40
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
15 1 19 23 34 36 42 24 33 10 26 22 11 9 21 38 25 40 20 31 8 3 18 4 17 30 7 35 37 27 28 39 5 16 29 2 32 6 12 41 13 14
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
32 6 21 13 39 2 26 1 17 16 31 30 10 4 3 24 27 14 19 20 34 37 25 18 12 8 9 22 35 11 15 33 38 7 36 23 42 29 40 28 41 5
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
6 34 14 26 22 13 41 39 25 36 4 19 18 10 23 1 24 20 9 8 38 17 42 5 11 12 31 2 28 37 40 3 32 35 7 33 29 27 16 21 15 30
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


Took 16.74757144s


PART 5: 10 latin squares of order 256:
PART 4: 1000 latin squares of order 256:


Generated in 6.581088256s
Took 1m9.236940447s
</pre>
</pre>

Revision as of 09:47, 15 August 2019

Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Section 3.3 of [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

F#

The Functions

<lang fsharp> // Jacobson and Matthews technique for generating Latin Squares. Nigel Galloway: August 5th., 2019 let R=let N=System.Random() in (fun n->N.Next(n)) let jmLS α X0= 

 let X0=Array2D.copy X0
 let N=let N=[|[0..α-1];[α-1..(-1)..0]|] in (fun()->N.[R 2])
 let rec randLS i j z i' j' z'=
   X0.[i,j']<-z'; X0.[i',j]<-z'
   match X0.[i',j']=z' with
    true->X0.[i',j']<-z; X0
   |false->randLS i' j' z' (List.find(fun n->X0.[n,j']=z')(N())) (List.find(fun n->X0.[i',n]=z')(N())) (if (R 2)=0 then let t=X0.[i',j'] in X0.[i',j']<-z; t else z)
 let i,j=R α,R α
 let z  =let z=1+(R (α-1)) in if z<X0.[i,j] then z else 1+(z+1)%α
 let i',j',z'=let N=[0..α-1] in (List.find(fun n->X0.[n,j]=z) N,List.find(fun n->X0.[i,n]=z) N,X0.[i,j])
 X0.[i,j]<-z; randLS i j z i' j' z'

let asNormLS α= 

 let n=Array.init (Array2D.length1 α) (fun n->(α.[n,0]-1,n))|>Map.ofArray
 let 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>

Output:
[[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
part 2

<lang fsharp> randLS 4 |> Seq.take 10000 |> Seq.map asNormLS |> Seq.countBy id |> Seq.iteri(fun n g->printf "%d(%d) " (n+1) (snd g)); printfn "" </lang>

Output:
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)
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>

Output:
 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

Go

The J & M implementation is based on the C code 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>

Output:

Sample run: 

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
Retrieved from "https://rosettacode.org/wiki/Latin_Squares_in_reduced_form/Randomizing_using_Jacobson_and_Matthews’_Technique?oldid=292155"