Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions
Content added Content deleted
(Promote to full task) |
|||
Line 773: | Line 773: | ||
10.811605 seconds (745.43 k allocations: 157.305 MiB, 0.30% gc time) |
10.811605 seconds (745.43 k allocations: 157.305 MiB, 0.30% gc time) |
||
</pre> |
</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} seconds."</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 seconds.</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |