Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique: Difference between revisions
Content added Content deleted
Line 513:
Generated in 6.581088256s
</pre>
=={{header|Phix}}==
{{trans|Go}}
<lang Phix>function shuffleCube(sequence c)
integer n = length(c), rx, ry, rz
bool proper = true
while true do
rx = rand(n)
ry = rand(n)
rz = rand(n)
if c[rx][ry][rz] == 0 then exit end if
end while
while true do
integer ox, oy, oz
for ox=1 to n do
if c[ox][ry][rz] == 1 then exit end if
end for
if not proper and rand(2)==2 then
for ox=ox+1 to n do
if c[ox][ry][rz] == 1 then exit end if
end for
end if
for oy=1 to n do
if c[rx][oy][rz] == 1 then exit end if
end for
if not proper and rand(2)==2 then
for oy=oy+1 to n do
if c[rx][oy][rz] == 1 then exit end if
end for
end if
for oz=1 to n do
if c[rx][ry][oz] == 1 then exit end if
end for
if not proper and rand(2)==2 then
for oz=oz+1 to n do
if c[rx][ry][oz] == 1 then exit end if
end for
end if
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 then
{rx, ry, rz} = {ox, oy, oz}
proper = false
else
proper = true
exit
end if
end while
return c
end function
function toMatrix(sequence c)
integer n = length(c)
sequence m = repeat(repeat(0,n),n)
for i=1 to n do
for j=1 to n do
for k=1 to n do
if c[i][j][k] != 0 then
m[i][j] = k
exit
end if
end for
end for
end for
return m
end function
function toReduced(sequence m)
integer n := length(m)
for j=1 to n-1 do
if m[1][j]!=j then
for k=j+1 to n do
if m[1][k]==j then
for i=1 to n do
{m[i][j], m[i][k]} = {m[i][k], m[i][j]}
end for
exit
end if
end for
end if
end for
for i=2 to n-1 do
if m[i][1]!=i then
for k=i+1 to n do
if m[k][1]==i then
for j=1 to n do
{m[i][j], m[k][j]} = {m[k][j], m[i][j]}
end for
exit
end if
end for
end if
end for
return m
end function
function makeCube(object from, integer n)
sequence c = repeat(repeat(repeat(0,n),n),n)
for i=1 to n do
for j=1 to n do
integer k = iff(from==NULL?mod(i+j,n)+1:from[i][j])
c[i][j][k] = 1
end for
end for
return c
end function
procedure main()
printf(1,"Part 1: 10,000 latin Squares of order 4 in reduced form:\n\n")
sequence from = {{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}},
c := makeCube(from, 4), m, rm, fk
integer freq = new_dict()
for i=1 to 10000 do
c = shuffleCube(c)
m = toMatrix(c)
rm = toReduced(m)
setd(rm,getd(rm,freq)+1,freq)
end for
fk = getd_all_keys(freq)
for i=1 to length(fk) do
printf(1,"%v occurs %d times\n", {fk[i],getd(fk[i],freq)})
end for
printf(1,"\nPart 2: 10,000 latin squares of order 5 in reduced form:\n\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}}
c = makeCube(from, 5)
destroy_dict(freq, justclear:=true)
for i=1 to 10000 do
c = shuffleCube(c)
m = toMatrix(c)
rm = toReduced(m)
setd(rm,getd(rm,freq)+1,freq)
end for
fk = getd_all_keys(freq)
for i=1 to length(fk) do
fk[i] = sprintf("%2d(%3d)", {i,getd(fk[i],freq)})
end for
puts(1,join_by(fk,8,7," ","\n"))
destroy_dict(freq)
-- part 3
printf(1,"\nPart 3: 750 latin squares of order 42, showing the last one:\n\n")
c = makeCube(NULL, 42)
for i=1 to 750 do
c = shuffleCube(c)
end for
m = toMatrix(c)
integer n := length(m)
for i=1 to n do
for j=1 to n do
m[i,j] = sprintf("%2d",m[i,j])
end for
m[i] = join(m[i]," ")
end for
printf(1,"%s\n",join(m,"\n"))
-- part 4
printf(1,"\nPART 4: 1000 latin squares of order 256:\n\n")
atom t0 = time()
c = makeCube(NULL, 256)
for i=1 to 1000 do
c = shuffleCube(c)
end for
printf(1,"Generated in %s\n", elapsed(time()-t0))
end procedure
main()</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,1,2},{4,3,2,1}} occurs 2503 times
{{1,2,3,4},{2,1,4,3},{3,4,2,1},{4,3,1,2}} occurs 2560 times
{{1,2,3,4},{2,3,4,1},{3,4,1,2},{4,1,2,3}} occurs 2510 times
{{1,2,3,4},{2,4,1,3},{3,1,4,2},{4,3,2,1}} occurs 2427 times
Part 2: 10,000 latin squares of order 5 in reduced form:
1(172) 9(197) 17(228) 25(166) 33(171) 41(224) 49(171)
2(168) 10(162) 18(216) 26(227) 34(172) 42(155) 50(226)
3(159) 11(198) 19(206) 27(165) 35(189) 43(190) 51(174)
4(170) 12(207) 20(159) 28(166) 36(177) 44(171) 52(196)
5(211) 13(148) 21(172) 29(173) 37(183) 45(189) 53(197)
6(169) 14(163) 22(128) 30(179) 38(184) 46(138) 54(173)
7(168) 15(155) 23(146) 31(170) 39(187) 47(170) 55(206)
8(193) 16(177) 24(146) 32(176) 40(157) 48(183) 56(177)
Part 3: 750 latin squares of order 42, showing the last one:
5 29 15 7 25 26 2 35 21 39 8 12 17 31 3 20 23 22 40 34 13 32 27 38 9 6 36 41 11 19 4 42 10 28 33 18 30 16 1 14 37 24
34 17 22 12 38 28 20 42 15 10 4 3 30 16 35 23 11 19 31 8 32 1 33 36 24 2 18 39 9 41 40 26 25 27 29 5 7 37 21 13 6 14
23 14 41 38 2 36 4 34 29 16 11 10 24 13 26 31 30 12 28 18 7 21 40 42 27 9 37 35 1 3 17 22 20 5 6 33 32 39 25 19 15 8
29 21 27 41 3 10 12 23 4 18 39 1 11 6 20 34 2 35 36 37 40 5 14 26 17 42 24 33 32 16 28 8 13 30 15 9 25 19 38 7 31 22
8 32 10 17 30 15 18 13 19 6 26 29 34 42 28 40 24 23 33 7 3 4 12 37 38 36 1 21 41 20 16 25 5 11 2 39 14 22 31 35 9 27
27 40 39 16 11 23 14 20 6 4 19 28 36 12 31 24 42 10 35 33 17 18 30 3 21 5 38 15 7 1 9 34 8 32 37 13 2 26 29 22 25 41
31 39 29 22 20 6 11 17 16 19 41 36 35 33 30 14 4 2 15 24 21 10 25 1 18 12 40 28 5 37 32 27 3 13 42 38 9 34 26 8 7 23
11 33 42 28 14 7 6 24 37 26 13 35 9 5 19 18 15 20 25 41 30 17 3 12 22 8 21 27 39 10 34 40 32 36 4 31 23 29 2 38 16 1
20 11 7 8 32 31 40 37 42 13 21 22 26 2 12 29 1 27 6 14 19 41 38 17 36 25 4 5 30 15 24 35 16 34 39 3 28 23 9 18 33 10
24 9 28 40 33 29 3 7 34 11 16 27 2 30 42 25 21 13 41 10 38 8 39 35 12 26 19 20 23 31 5 32 1 22 14 6 4 15 37 36 17 18
2 8 23 37 27 9 38 36 13 24 31 14 29 7 6 42 3 34 18 32 1 20 22 41 25 30 33 16 15 4 11 10 26 39 21 28 17 40 19 5 12 35
13 2 26 15 10 40 39 6 33 29 42 34 12 17 11 28 22 32 14 25 24 37 21 5 8 23 30 9 18 7 41 31 4 3 27 19 16 35 20 1 38 36
22 23 34 31 28 25 36 38 9 32 30 8 3 11 17 41 26 39 24 6 2 35 13 4 7 21 29 18 14 27 19 37 15 20 16 12 10 33 40 42 1 5
36 28 20 11 29 39 22 41 35 7 5 15 31 24 8 19 27 37 1 38 16 13 6 2 32 40 14 25 33 17 21 4 34 23 30 10 18 42 12 9 26 3
6 25 8 2 17 33 19 12 1 38 40 39 5 32 18 7 34 30 9 11 15 3 31 23 37 24 27 14 20 28 36 16 21 42 13 29 41 4 35 10 22 26
14 24 38 32 12 3 15 2 17 28 36 40 19 26 1 27 29 41 8 5 23 42 20 13 10 34 6 31 16 35 30 7 11 18 22 21 33 25 4 37 39 9
39 30 5 20 1 22 9 40 36 27 7 33 37 18 29 38 25 42 4 21 14 31 10 28 26 15 16 8 3 13 35 19 41 2 32 24 12 11 17 23 34 6
35 18 17 14 13 41 25 31 2 3 32 24 10 19 22 33 6 1 16 23 9 15 8 39 5 7 11 12 42 34 37 28 38 4 26 20 40 36 27 21 30 29
9 19 24 26 42 16 7 30 10 40 29 4 33 8 38 22 14 25 37 28 5 27 41 32 1 13 17 36 34 39 23 11 31 6 35 2 20 21 18 15 3 12
12 22 37 1 4 20 32 3 30 25 28 26 6 14 36 11 39 21 38 29 27 24 7 16 15 31 9 34 10 33 13 18 40 35 5 17 19 8 42 41 23 2
3 16 31 42 7 17 37 25 23 36 15 18 27 22 5 21 40 9 10 39 4 26 29 6 2 33 41 19 35 8 12 20 28 38 24 32 11 1 34 30 14 13
19 41 36 34 21 18 26 29 27 20 14 16 38 40 7 15 32 3 17 4 10 28 35 33 13 22 8 6 25 42 31 23 2 37 9 30 1 12 5 24 11 39
25 4 12 29 26 37 16 9 22 30 6 23 40 21 15 35 20 38 19 42 11 2 1 18 3 41 5 10 28 36 33 39 27 24 34 8 31 32 14 17 13 7
41 12 14 33 40 35 28 15 7 9 1 5 13 23 27 32 8 17 26 31 42 34 37 19 30 38 20 22 2 6 39 21 36 29 18 16 3 24 11 4 10 25
26 20 3 19 16 30 5 14 8 41 10 7 25 15 21 13 38 36 39 22 28 23 17 27 33 37 34 32 4 2 29 12 9 31 1 42 24 18 6 40 35 11
10 1 25 36 37 24 8 26 3 12 34 42 18 38 41 16 9 14 32 35 31 30 5 22 39 27 7 4 13 29 6 15 23 19 28 11 21 2 33 20 40 17
37 35 40 13 39 8 31 33 38 15 12 32 16 41 34 6 5 11 30 27 20 22 26 14 29 18 28 23 36 21 25 2 7 1 17 4 42 9 10 3 24 19
30 34 2 24 35 1 23 10 20 42 22 37 15 39 9 17 12 4 5 26 18 38 16 29 31 3 25 11 21 14 8 41 6 40 19 7 13 27 28 32 36 33
16 7 19 21 18 27 29 22 39 35 2 38 28 20 40 9 36 8 12 1 41 33 15 31 11 10 42 24 6 32 26 17 37 14 25 23 5 13 3 34 4 30
32 3 11 25 5 12 1 4 18 31 33 19 41 9 37 10 7 24 13 40 6 16 42 21 34 20 26 2 38 22 15 14 35 17 23 36 8 30 39 27 29 28
1 13 30 39 36 4 34 32 12 14 17 6 23 27 24 3 41 40 11 20 22 9 28 15 42 16 2 29 31 5 7 33 19 21 10 35 26 38 8 25 18 37
18 38 4 23 41 19 35 21 26 33 37 20 42 28 13 5 10 7 3 15 25 39 32 9 14 17 31 40 29 24 1 36 30 8 12 34 27 6 22 11 2 16
4 27 21 3 8 42 41 16 40 37 18 2 22 25 32 36 17 5 23 30 29 6 9 34 19 35 15 13 24 11 14 1 12 10 38 26 39 20 7 33 28 31
40 26 9 30 6 21 42 19 5 2 3 31 4 35 23 37 28 15 20 13 34 12 11 8 16 14 39 17 22 25 27 38 18 33 7 1 36 10 24 29 41 32
28 15 1 4 19 11 24 5 31 8 23 17 21 34 14 26 37 18 7 2 35 29 36 10 6 39 32 30 27 38 3 9 33 16 20 25 22 41 13 12 42 40
21 10 35 27 31 2 13 39 28 5 9 41 1 36 4 8 19 29 34 16 33 40 24 25 20 11 22 7 12 18 42 30 14 26 3 37 15 17 23 6 32 38
17 42 18 6 23 5 33 1 24 34 35 30 7 37 16 12 31 26 21 19 39 14 4 11 41 32 10 3 40 9 38 13 22 25 36 27 29 28 15 2 8 20
42 6 13 35 22 32 10 8 14 21 24 11 39 1 2 4 18 33 27 9 12 25 23 40 28 29 3 26 37 30 20 5 17 41 31 15 38 7 36 16 19 34
7 36 16 5 9 34 21 11 32 22 20 25 8 10 33 30 35 31 29 12 26 19 2 24 4 1 13 38 17 23 18 6 39 15 40 14 37 3 41 28 27 42
15 37 32 9 24 38 27 28 41 17 25 13 20 29 10 39 33 6 2 36 8 7 18 30 35 4 23 1 19 26 22 3 42 12 11 40 34 14 16 31 5 21
33 31 6 18 34 14 17 27 25 1 38 21 32 4 39 2 13 16 42 3 36 11 19 7 23 28 12 37 8 40 10 29 24 9 41 22 35 5 30 26 20 15
38 5 33 10 15 13 30 18 11 23 27 9 14 3 25 1 16 28 22 17 37 36 34 20 40 19 35 42 26 12 2 24 29 7 8 41 6 31 32 39 21 4
PART 4: 1000 latin squares of order 256:
Generated in 19.5s
</pre>
Unfortunately the last part of this task exposes the relatively poor performance of subscripting in phix.
| |||