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:45, 11 May 2021

12,357 bytes added ,  3 years ago
Added Wren
m (→‎{{header|Phix}}: added syntax colouring the hard way)
(Added Wren)
Line 1,022:
</pre>
Unfortunately the last part of this task exposes the relatively poor performance of subscripting in phix.
 
=={{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>
PureFox
9,487

edits

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