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

=={{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>