Latin Squares in reduced form: Difference between revisions
julia example
m (added whitespace before the table of contents (TOC).) |
(julia example) |
||
Line 396:
Order 5: Size 56 x 5! x 4! => Total 161280
Order 6: Size 9408 x 6! x 5! => Total 812851200
</pre>
=={{header|Julia}}==
<lang julia>using Combinatorics
clash(row2, row1::Vector{Int}) = any(i -> row1[i] == row2[i], 1:length(row2))
clash(row, rows::Vector{Vector{Int}}) = any(r -> clash(row, r), rows)
permute_onefixed(i, n) = map(vec -> vcat(i, vec), permutations(filter(x -> x != i, 1:n)))
filter_permuted(rows, i, n) = filter(v -> !clash(v, rows), permute_onefixed(i, n))
firstmat(n) = reshape(collect(1:n), 1, n)
function makereducedlatinsquares(n)
matarray = [firstmat(n)]
for i in 2:n
newmatarray = Vector{Matrix{Int}}()
for mat in matarray
r = size(mat)[1] + 1
newrows = filter_permuted(collect(row[:] for row in eachrow(mat)), r, n)
newmat = zeros(Int, r, n)
newmat[1:r-1, :] .= mat
append!(newmatarray,
[deepcopy(begin newmat[i, :] .= row; newmat end) for row in newrows])
end
matarray = newmatarray
end
matarray, length(matarray)
end
function testlatinsquares()
squares, count = makereducedlatinsquares(4)
println("The four reduced latin squares of order 4 are:")
for sq in squares, (i, row) in enumerate(eachrow(sq)), j in 1:4
print(row[j], j == 4 ? (i == 4 ? "\n\n" : "\n") : " ")
end
for i in 1:6
squares, count = makereducedlatinsquares(i)
println("Order $i: Size ", rpad(count, 5), "* $(i)! * $(i - 1)! = ",
count * factorial(i) * factorial(i - 1))
end
end
testlatinsquares()
</lang>{{out}}
<pre>
The four reduced latin squares of order 4 are:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
2 1 4 3
3 4 2 1
4 3 1 2
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
Order 1: Size 1 * 1! * 0! = 1
Order 2: Size 1 * 2! * 1! = 2
Order 3: Size 1 * 3! * 2! = 12
Order 4: Size 4 * 4! * 3! = 576
Order 5: Size 56 * 5! * 4! = 161280
Order 6: Size 9408 * 6! * 5! = 812851200
</pre>
| |||