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

</pre>

=={{header|Julia}}==

{{trans|Go}}

const Cube = Vector{Vector{Vector{Int}}}

const Mat = Vector{Vector{Int}}

const Vec = Int[]

function reduced(m::Mat)

n = length(m)

r = deepcopy(m)

for j in 1:n-1

if r[1][j] != j

for k in j+1:n

if r[1][k] == j

for i in 1:n

r[i][j], r[i][k] = r[i][k], r[i][j]

end

break

end

end

end

end

for i in 2:n-1

if r[i][1] != i

for k in i+1:n

if r[k][1] == i

for j in 1:n

r[i][j], r[k][j] = r[k][j], r[i][j]

end

break

end

end

end

end

return r

end

""" print matrix as small integers, no punctuation """

function print_matrix(m::Mat)

n = length(m)

padding = max(2, Int(ceil(log(10, n+1))) + 1)

for i in 1:n

for j in 1:n

print(lpad(m[i][j], padding))

end

println()

end

println()

end

function shuffle_cube(c::Cube)

n = length(c)

proper = true

rx, ry, rz = 0, 0, 0

while true

rx, ry, rz = rand(1:n, 3)

c[rx][ry][rz] == 0 && break

end

while true

ox = something(findfirst(i -> c[i][ry][rz] == 1, 1:n), n)

oy = something(findfirst(i -> c[rx][i][rz] == 1, 1:n), n)

oz = something(findfirst(i -> c[rx][ry][i] == 1, 1:n), n)

if !proper

rand() < 1/2 && (ox = something(findlast(i -> c[i][ry][rz] == 1, 1:n), n))

rand() < 1/2 && (oy = something(findlast(i -> c[rx][i][rz] == 1, 1:n), n))

rand() < 1/2 && (oz = something(findlast(i -> c[rx][ry][i] == 1, 1:n), n))

end

c[rx][ry][rz] += 1

c[rx][oy][oz] += 1

c[ox][ry][oz] += 1

c[ox][oy][rz] += 1

c[rx][ry][oz] -= 1

c[rx][oy][rz] -= 1

c[ox][ry][rz] -= 1

c[ox][oy][oz] -= 1

if c[ox][oy][oz] < 0

rx, ry, rz = ox, oy, oz

proper = false

else

proper = true

break

end

end

end

function matrix(c::Cube)::Mat

n = length(c)

m = [[0 for i in 1:n] for j in 1:n]

for i in 1:n, j in 1:n

for k in 1:n

if c[i][j][k] != 0

m[i][j] = k

break

end

end

end

return m

end

function cube(from, n)

c = [[[0 for i in 1:n] for j in 1:n] for k in 1:n]

for i in 1:n, j in 1:n

k = (from isa Nothing) ? mod1(i + j, n) : from[i][j]

c[i][j][k] = 1

end

return c

end

function testJacobsenMatthews()

# part 1

println("PART 1: 10,000 latin Squares of order 4 in reduced form:\n")

from = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 4, 1, 2], [4, 3, 2, 1]]

freqs4 = Dict{Array, Int}()

c = cube(from, 4)

for i in 1:10000

shuffle_cube(c)

m = matrix(c)

rm = reduced(m)

n = get!(freqs4, rm, 0)

freqs4[rm] = n + 1

end

for (a, freq) in freqs4

print_matrix(a)

println("Occurs $freq times\n")

end

# part 2

println("\nPART 2: 10,000 latin squares of order 5 in reduced form:\n")

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]]

freqs5 = Dict{Array, Int}()

c = cube(from, 5)

for i in 1:10000

shuffle_cube(c)

m = matrix(c)

rm = reduced(m)

n = get!(freqs5, rm, 0)

freqs5[rm] = n + 1

end

for (i, freq) in enumerate(sort(collect(values(freqs5))))

i > 1 && (print(", "); (i - 1) % 8 == 0 && println())

print(lpad(i, 2), "(", lpad(freq, 3), ")")

end

println("\n")

# part 3

println("\nPART 3: 750 latin squares of order 42, showing the last one:\n")

m42 = [[0 for i in 1:42] for j in 1:42]

c = cube(nothing, 42)

for i in 1:750

shuffle_cube(c)

i == 750 && (m42 = tomatrix(c))

end

print_matrix(m42)

# part 4

println("\nPART 4: 1000 latin squares of order 256:\n")

@time begin

c = cube(nothing, 256)

for i in 1:1000

shuffle_cube(c)

end

end

end

testJacobsenMatthews()

</lang>{{out}}

<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 2508 times

1 2 3 4

2 1 4 3

3 4 2 1

4 3 1 2

Occurs 2427 times

1 2 3 4

2 1 4 3

3 4 1 2

4 3 2 1

Occurs 2529 times

1 2 3 4

2 3 4 1

3 4 1 2

4 1 2 3

Occurs 2536 times

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

1(152), 2(152), 3(153), 4(154), 5(158), 6(160), 7(160), 8(160),

9(162), 10(165), 11(166), 12(167), 13(168), 14(170), 15(170), 16(172),

17(172), 18(173), 19(174), 20(174), 21(175), 22(177), 23(177), 24(177),

25(177), 26(178), 27(179), 28(180), 29(180), 30(181), 31(181), 32(182),

33(182), 34(182), 35(183), 36(184), 37(185), 38(185), 39(185), 40(186),

41(187), 42(187), 43(187), 44(188), 45(189), 46(189), 47(190), 48(195),

49(195), 50(197), 51(197), 52(199), 53(199), 54(199), 55(201), 56(203)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

PART 4: 1000 latin squares of order 256:

10.811605 seconds (745.43 k allocations: 157.305 MiB, 0.30% gc time)