Random Latin squares

From Rosetta Code
Revision as of 11:30, 9 June 2019 by rosettacode>Paddy3118 (New draft task with python example.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
  1. Generate a function/routine/proceedure/method/... that given n generates a randomised Latin square of size n.
  2. 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