Rosetta Code

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

Page Discussion

Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique (view source)

Revision as of 21:39, 7 August 2019

13,400 bytes added ,  4 years ago
→‎{{header|Go}}: Added a second much quicker but less uniform version.
(Added a partial solution for Go)
(→‎{{header|Go}}: Added a second much quicker but less uniform version.)
Line 128:
 
=={{header|Go}}==
===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.
 
Line 494 ⟶ 495:
 
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
2 4 1 3
3 1 4 2
4 3 2 1
 
Occurs 2976 times
 
1 2 3 4
2 1 4 3
3 4 2 1
4 3 1 2
 
Occurs 3090 times
 
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
 
Occurs 3053 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:
 
1(237), 2(170), 3(160), 4(181), 5(174), 6(211), 7(191), 8(153),
9(162), 10(153), 11(175), 12(184), 13(169), 14(162), 15(174), 16(168),
17(177), 18(178), 19(185), 20(169), 21(234), 22(186), 23(173), 24(180),
25(184), 26(166), 27(176), 28(172), 29(154), 30(145), 31(148), 32(165),
33(166), 34(175), 35(154), 36(176), 37(166), 38(162), 39(180), 40(206),
41(191), 42(236), 43(179), 44(223), 45(165), 46(148), 47(181), 48(173),
49(164), 50(226), 51(175), 52(177), 53(239), 54(169), 55(171), 56(182)
 
 
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
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
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
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
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
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
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
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
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
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
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 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
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
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
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
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
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
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
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 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
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
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
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
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
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
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
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
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
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
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 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
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
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
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
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
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
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
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
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
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
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
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
 
Took 16.74757144s
 
PART 5: 10 latin squares of order 256:
 
Took 1m9.236940447s
</pre>
PureFox
9,490

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/292154"