Random Latin squares
Random Latin squares is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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 Lstin 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
n
generates a randomised Latin square of sizen
. - Use the function to generate and show here, two randomly generated squares of size 5.
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