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 configurations 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/procedure/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.
- Note
Strict Uniformity in the random generation is a hard problem and not a requirement of the task.
- 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],] };
sub random ( @ls, :$size = 5 ) {
# Build
for 1 ..^ $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 = ('A' .. 'Z').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, 2, 1;</lang>
- Sample output:
N I M L B L N I B M B L N M I M B L I N I M B N L S U N N S U U N S C X A A C X X A C I W X P N O Z D J P D N Z O W J I X J P W X D I N Z O D O J I X N P W Z N J I O P Z W X D Z I O J W D X P N W N Z D J X I O P X Z D N I P O J W O X P W Z J D N I U Z B K D G P Y Q C X F A E A F Z U G Y C Q K X B E D P Z A U B E P Y C X Q K D F G K B X Q A D E G Y P C Z U F B U K X F E G P C Y Q A Z D E G D F C X K B Z U A Y P Q D E F A Y Q X K U B Z P G C G P E D Q K B U A Z F C Y X P Y G E X B U Z F A D Q C K C Q Y P B Z A F E D G K X U X K Q C Z F D E P G Y U B A Y C P G K U Z A D F E X Q B Q X C Y U A F D G E P B K Z F D A Z P C Q X B K U G E Y T F F T J
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