Random Latin squares
A Latin square of size n is an arrangement of n symbols in an n-by-n square in such a way that each row and column has each symbol appearing exactly once.
A randomised Latin square generates random configuartions of the symbols for such a Latin square
- Example n=4 randomised Latin square
0 2 3 1 2 1 0 3 3 0 1 2 1 3 2 0
- Task
- Generate a function/routine/proceedure/method/... that given
ngenerates a randomised Latin square of sizen. - Use the function to generate and show here, two randomly generated squares of size 5.
- Reference
Julia
Using the Python algorithm as described in the discussion section. <lang julia>using Random
shufflerows(mat) = mat[shuffle(1:end), :] shufflecols(mat) = mat[:, shuffle(1:end)]
function addatdiagonal(mat)
n = size(mat)[1] + 1
newmat = similar(mat, size(mat) .+ 1)
for j in 1:n, i in 1:n
newmat[i, j] = (i == n && j < n) ? mat[1, j] : (i == j) ? n - 1 :
(i < j) ? mat[i, j - 1] : mat[i, j]
end
newmat
end
function makelatinsquare(N)
mat = [0 1; 1 0]
for i in 3:N
mat = addatdiagonal(mat)
end
shufflecols(shufflerows(mat))
end
function printlatinsquare(N)
mat = makelatinsquare(N)
for i in 1:N, j in 1:N
print(rpad(mat[i, j], 3), j == N ? "\n" : "")
end
end
printlatinsquare(5), println("\n"), printlatinsquare(5)
</lang>
- Output:
1 3 0 4 2 3 0 4 2 1 0 4 2 1 3 2 1 3 0 4 4 2 1 3 0 2 0 1 3 4 4 3 2 1 0 3 2 0 4 1 1 4 3 0 2 0 1 4 2 3
Perl 6
<lang perl6>sub latin-square { [[0,1], [1,0]] };
sub random ( @ls, :$size = 5 ) {
# Build
for 2 ..^ $size -> $i {
@ls[$i] = @ls[0].clone;
@ls[$_].splice($_, 0, $i) for 0 .. $i;
}
# Shuffle @ls = @ls[^$size .pick(*)]; my @cols = ^$size .pick(*); @ls[$_] = @ls[$_][@cols] for ^@ls;
# Some random Latin glyphs
my @symbols = ('Ŋ' .. 'ž').pick($size);
@ls.deepmap: { $_ = @symbols[$_] };
}
sub display ( @array ) { $_.fmt("%2s ").put for |@array, }
- The Task
- Default size 5
display random latin-square;
- Specified size
display random :size($_), latin-square for 3, 3;
- Or, if you'd prefer:
display random latin-square, :size($_) for 9, 14;</lang>
- Sample output:
Ř ŝ ŷ ű ŭ ŷ ű ŭ Ř ŝ ŭ Ř ŝ ŷ ű ű ŭ Ř ŝ ŷ ŝ ŷ ű ŭ Ř ŋ ŗ ŭ ŗ ŭ ŋ ŭ ŋ ŗ Ř ő Ū Ū Ř ő ő Ū Ř Ŵ Ÿ Ţ ů ş Ū ţ ŧ ű ŧ Ţ ů Ÿ Ŵ ű Ū ş ţ Ū ş Ŵ ŧ ţ ů Ţ ű Ÿ ů ţ Ū ű Ţ ŧ Ŵ Ÿ ş ş ů Ÿ Ţ ŧ ţ ű Ŵ Ū ţ ŧ ş Ŵ ű Ţ Ÿ Ū ů Ţ ű ţ Ū Ÿ Ŵ ş ů ŧ Ÿ Ū ű ţ ů ş ŧ Ţ Ŵ ű Ŵ ŧ ş Ū Ÿ ů ţ Ţ ō Ş ū ŝ Ŝ ś Ž ř Ś š Ů ž Ō Ŗ Ŗ ś Ō ū ř Ů Ś ž Ŝ ō š ŝ Ş Ž ś ŝ ř Ŝ Ŗ ū š Ž ō Ş Ō Ś ž Ů Ş ž Ŝ Ś ō ŝ Ů Ŗ š Ō ū Ž ř ś Ŝ ō Ů ś ū Ŗ ž Ō ŝ Ś Ž Ş š ř Ś š ś Ş ŝ ō ř ū ž Ž Ŗ Ō Ů Ŝ Ž Ů Ş Ō ž š Ŝ ŝ ř Ŗ ō ū ś Ś š Ō ŝ ž Ś Ş Ŗ Ŝ Ž Ů ś ř ū ō ū Ŝ Ž Ŗ Ů ř Ş š ś ŝ ž ō Ś Ō ŝ Ś Ŗ ō ś Ŝ Ō Ů Ş ž ř š Ž ū ž Ž ō š Ş Ś ū ś Ō ř Ŝ Ů Ŗ ŝ ř Ŗ š Ů Ō Ž ŝ Ş ū Ŝ Ś ś ō ž Ů ū ž ř Ž Ō ō Ś Ŗ ś Ş Ŝ ŝ š Ō ř Ś Ž š ž ś ō Ů ū ŝ Ŗ Ŝ Ş
Python
<lang python>from random import choice, shuffle from copy import deepcopy
def rls(n):
if n <= 0:
return []
else:
symbols = list(range(n))
square = _rls(symbols)
return _shuffle_transpose_shuffle(square)
def _shuffle_transpose_shuffle(matrix):
square = deepcopy(matrix) shuffle(square) trans = list(zip(*square)) shuffle(trans) return trans
def _rls(symbols):
n = len(symbols)
if n == 1:
return [symbols]
else:
sym = choice(symbols)
symbols.remove(sym)
square = _rls(symbols)
square.append(square[0].copy())
for i in range(n):
square[i].insert(i, sym)
return square
def _to_text(square):
if square:
width = max(len(str(sym)) for row in square for sym in row)
txt = '\n'.join(' '.join(f"{sym:>{width}}" for sym in row)
for row in square)
else:
txt =
return txt
def _check(square):
transpose = list(zip(*square))
assert _check_rows(square) and _check_rows(transpose), \
"Not a Latin square"
def _check_rows(square):
if not square:
return True
set_row0 = set(square[0])
return all(len(row) == len(set(row)) and set(row) == set_row0
for row in square)
if __name__ == '__main__':
for i in [3, 3, 5, 5, 12]:
square = rls(i)
print(_to_text(square))
_check(square)
print()</lang>
- Output:
2 1 0 0 2 1 1 0 2 1 0 2 0 2 1 2 1 0 1 0 3 2 4 3 4 2 0 1 4 2 1 3 0 2 1 0 4 3 0 3 4 1 2 2 1 0 4 3 0 4 3 2 1 3 2 1 0 4 4 3 2 1 0 1 0 4 3 2 6 2 4 8 11 9 3 1 7 0 5 10 1 11 5 2 8 6 0 9 4 10 7 3 2 7 10 5 4 8 9 11 0 6 3 1 8 5 0 4 7 11 1 2 3 9 10 6 11 4 3 7 5 2 6 8 10 1 0 9 10 1 8 6 9 0 7 3 11 4 2 5 7 0 1 3 10 5 8 4 6 2 9 11 9 8 7 11 2 1 10 6 5 3 4 0 3 9 2 1 6 10 4 0 8 5 11 7 5 3 6 10 0 4 11 7 9 8 1 2 4 10 9 0 3 7 2 5 1 11 6 8 0 6 11 9 1 3 5 10 2 7 8 4