Random Latin Squares

From Rosetta Code
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 Latin square generates random configurations of the symbols for any given n.

Example n=4 randomised Latin square
0 2 3 1
2 1 0 3
3 0 1 2
1 3 2 0
Task
  1. Create a function/routine/procedure/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.
Note

Strict Uniformity in the random generation is a hard problem and not a requirement of the task.

Reference


Factor[edit]

The initial approach is simple: generate a random permutation, one row at a time. If a row conflicts with any of the rows above it, generate a new random permutation for that row. The upside is that this is easy to understand and generates uniformly-random Latin squares. The downside is that it is an exponential time algorithm.

If larger sizes are desired, non-uniform approaches may be used. The Koscielny product is one such approach that "multiplies" two Latin squares together to produce a larger one. The algorithm is described here. The two initial order-5 squares are multiplied using this method to produce an order-25 square.

USING: arrays io kernel locals math math.matrices prettyprint
random sequences sets vectors ;
IN: rosetta-code.random-latin-squares
 
: add-row ( matrix -- matrix' )
dup last clone suffix!
[ dup [ all-unique? ] column-map [ f = ] any? ]
[ [ length 1 - ] [ [ [ randomize ] change-nth ] keep ] bi ]
while ;
 
! Small optimization: there is only 1 choice for the last row.
: add-last-row ( matrix -- matrix' )
dup dim second <iota> over [ diff first ] with column-map
suffix! ;
 
: last-row? ( matrix -- ? ) dim first2 = ;
 
: latin ( n -- matrix )
[ <iota> >array randomize 1vector ] [
1 - [ dup last-row? [ add-last-row ] [ add-row ] if ]
times
] bi ;
 
:: koscielny-product ( ls1 ls2 -- prod )
ls1 ls2 [ dim first ] [email protected] :> ( n1 n2 )
n1 n2 [ sq ] [email protected] zero-matrix :> prod
n1 n2 * <iota> [
 :> i n1 n2 * <iota> [
 :> j
n2 i n2 /i j n2 /i ls1 nth nth *
i n2 mod j n2 mod ls2 nth nth +
{ i j } prod set-index
] each
] each prod ;
 
: random-latin-squares ( -- )
"Random Latin squares via \"restarting row\" method:"
print 5 5 [ latin dup simple-table. nl ] [email protected]
"Koscielny product of previous squares:" print
koscielny-product simple-table. ;
 
MAIN: random-latin-squares
Output:
Random Latin squares via "restarting row" method:
1 0 2 3 4
3 2 4 1 0
2 4 1 0 3
4 3 0 2 1
0 1 3 4 2

2 4 1 3 0
0 1 3 4 2
3 0 2 1 4
4 3 0 2 1
1 2 4 0 3

Koscielny product of previous squares:
7  5  8  9  6  17 15 18 19 16 12 10 13 14 11 22 20 23 24 21 2  0  3  4  1
9  6  5  8  7  19 16 15 18 17 14 11 10 13 12 24 21 20 23 22 4  1  0  3  2
6  8  7  5  9  16 18 17 15 19 11 13 12 10 14 21 23 22 20 24 1  3  2  0  4
8  9  6  7  5  18 19 16 17 15 13 14 11 12 10 23 24 21 22 20 3  4  1  2  0
5  7  9  6  8  15 17 19 16 18 10 12 14 11 13 20 22 24 21 23 0  2  4  1  3
2  0  3  4  1  12 10 13 14 11 22 20 23 24 21 17 15 18 19 16 7  5  8  9  6
4  1  0  3  2  14 11 10 13 12 24 21 20 23 22 19 16 15 18 17 9  6  5  8  7
1  3  2  0  4  11 13 12 10 14 21 23 22 20 24 16 18 17 15 19 6  8  7  5  9
3  4  1  2  0  13 14 11 12 10 23 24 21 22 20 18 19 16 17 15 8  9  6  7  5
0  2  4  1  3  10 12 14 11 13 20 22 24 21 23 15 17 19 16 18 5  7  9  6  8
12 10 13 14 11 22 20 23 24 21 7  5  8  9  6  2  0  3  4  1  17 15 18 19 16
14 11 10 13 12 24 21 20 23 22 9  6  5  8  7  4  1  0  3  2  19 16 15 18 17
11 13 12 10 14 21 23 22 20 24 6  8  7  5  9  1  3  2  0  4  16 18 17 15 19
13 14 11 12 10 23 24 21 22 20 8  9  6  7  5  3  4  1  2  0  18 19 16 17 15
10 12 14 11 13 20 22 24 21 23 5  7  9  6  8  0  2  4  1  3  15 17 19 16 18
17 15 18 19 16 7  5  8  9  6  2  0  3  4  1  12 10 13 14 11 22 20 23 24 21
19 16 15 18 17 9  6  5  8  7  4  1  0  3  2  14 11 10 13 12 24 21 20 23 22
16 18 17 15 19 6  8  7  5  9  1  3  2  0  4  11 13 12 10 14 21 23 22 20 24
18 19 16 17 15 8  9  6  7  5  3  4  1  2  0  13 14 11 12 10 23 24 21 22 20
15 17 19 16 18 5  7  9  6  8  0  2  4  1  3  10 12 14 11 13 20 22 24 21 23
22 20 23 24 21 2  0  3  4  1  17 15 18 19 16 7  5  8  9  6  12 10 13 14 11
24 21 20 23 22 4  1  0  3  2  19 16 15 18 17 9  6  5  8  7  14 11 10 13 12
21 23 22 20 24 1  3  2  0  4  16 18 17 15 19 6  8  7  5  9  11 13 12 10 14
23 24 21 22 20 3  4  1  2  0  18 19 16 17 15 8  9  6  7  5  13 14 11 12 10
20 22 24 21 23 0  2  4  1  3  15 17 19 16 18 5  7  9  6  8  10 12 14 11 13

Go[edit]

As the task is not asking for large squares to be generated and even n = 10 is virtually instant, we use a simple brute force approach here which has the merit of being completely random.

package main
 
import (
"fmt"
"math/rand"
"time"
)
 
type matrix [][]int
 
func shuffle(row []int, n int) {
rand.Shuffle(n, func(i, j int) {
row[i], row[j] = row[j], row[i]
})
}
 
func latinSquare(n int) {
if n <= 0 {
fmt.Println("[]\n")
return
}
latin := make(matrix, n)
for i := 0; i < n; i++ {
latin[i] = make([]int, n)
if i == n-1 {
break
}
for j := 0; j < n; j++ {
latin[i][j] = j
}
}
// first row
shuffle(latin[0], n)
 
// middle row(s)
for i := 1; i < n-1; i++ {
shuffled := false
shuffling:
for !shuffled {
shuffle(latin[i], n)
for k := 0; k < i; k++ {
for j := 0; j < n; j++ {
if latin[k][j] == latin[i][j] {
continue shuffling
}
}
}
shuffled = true
}
}
 
// last row
for j := 0; j < n; j++ {
used := make([]bool, n)
for i := 0; i < n-1; i++ {
used[latin[i][j]] = true
}
for k := 0; k < n; k++ {
if !used[k] {
latin[n-1][j] = k
break
}
}
}
printSquare(latin, n)
}
 
func printSquare(latin matrix, n int) {
for i := 0; i < n; i++ {
fmt.Println(latin[i])
}
fmt.Println()
}
 
func main() {
rand.Seed(time.Now().UnixNano())
latinSquare(5)
latinSquare(5)
latinSquare(10) // for good measure
}
Output:
[3 2 1 0 4]
[0 3 2 4 1]
[4 1 0 3 2]
[2 4 3 1 0]
[1 0 4 2 3]

[3 1 0 4 2]
[1 0 2 3 4]
[2 4 3 0 1]
[4 3 1 2 0]
[0 2 4 1 3]

[9 2 8 4 6 1 7 5 0 3]
[4 3 7 6 0 8 5 9 2 1]
[2 1 9 7 3 4 6 0 5 8]
[8 6 0 5 7 2 3 1 9 4]
[5 0 6 8 1 3 9 2 4 7]
[7 5 4 9 2 0 1 3 8 6]
[3 9 2 1 5 6 8 4 7 0]
[1 4 5 2 8 7 0 6 3 9]
[6 8 3 0 4 9 2 7 1 5]
[0 7 1 3 9 5 4 8 6 2]

Julia[edit]

Using the Python algorithm as described in the discussion section.

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)
 
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

M2000 Interpreter[edit]

Easy Way[edit]

One row shuffled to be used as the destination row. One more shuffled and then n times rotated by one and stored to array

for 40x40 need 2~3 sec, including displaying to screen

We use the stack of values, a linked list, for pushing to top (Push) or to bottom (Data), and we can pop from top using Number or by using Read A to read A from stack. Also we can shift from a chosen position to top using Shift, or using shiftback to move an item from top to chosen position. So we shuffle items by shifting them.

 
Module FastLatinSquare {
n=5
For k=1 To 2
latin()
Next
n=40
latin()
Sub latin()
Local i,a, a(1 To n), b, k
Profiler
flush
Print "latin square ";n;" by ";n
For i=1 To n
Push i
Next i
For i=1 To n div 2
Shiftback random(2, n)
Next i
a=[]
Push ! stack(a)
a=array(a) ' change a from stack to array
For i=1 To n*10
Shiftback random(2, n)
Next i
For i=0 To n-1
Data number ' rotate by one the stack items
b=[] ' move stack To b, leave empty stack
a(a#val(i))=b
Push ! stack(b) ' Push from a copy of b all items To stack
Next i
flush
For k=1 To n div 2
z=random(2, n)
For i=1 To n
a=a(i)
stack a {
shift z
}
Next
Next
For i=1 To n
a=a(i)
a(i)=array(a) ' change To array from stack
Next i
For i=1 To n
Print a(i)
Next i
Print TimeCount
End Sub
}
FastLatinSquare

Hard Way[edit]

for 5x5 need some miliseconds

for 16X16 need 56 seconds

for 20X20 need 22 min (as for 9.8 version)

 
Module LatinSquare (n, z=1, f$="latin.dat", NewFile As Boolean=False) {
If Not Exist(f$) Or NewFile Then
Open f$ For Wide Output As f
Else
Open f$ For Wide Append As f
End If
ArrayToString=Lambda -> {
Shift 2 ' swap two top values in stack
Push Letter$+Str$(Number)
}
Dim line(1 to n)
flush ' erase current stack of value
z=if(z<1->1, z)
newColumn()
For j=1 To z
Profiler
ResetColumns()
For i=1 To n
placeColumn()
Next
Print "A latin square of ";n;" by ";n
For i=1 To n
Print line(i)
Print #f, line(i)#Fold$(ArrayToString)
Next
Print TimeCount
Refresh
Next
close #f
Flush ' empty stack again
End
Sub ResetColumns()
Local i
For i=1 To n:line(i)=(,):Next
End Sub
Sub newColumn()
Local i
For i=1 To n : Push i: Next
End Sub
Sub shuffle()
Local i
For i=1 To n div 2: Shift Random(2, n): Next
End Sub
Sub shuffleLocal(x)
If Stack.size<=x Then Exit Sub
Shift Random(x+1, Stack.size)
Shiftback x
End Sub
Sub PlaceColumn()
Local i, a, b, k
shuffle()
Do
data number ' rotate one position
k=0
For i=1 To n
a=line(i) ' get the pointer
Do
If a#Pos(Stackitem(i))=-1 Then k=0 :Exit Do
shuffleLocal(i)
k++
Until k>Stack.size-i
If k>0 Then Exit For
Next
Until k=0
For i=1 To n
a=line(i)
Append a, (Stackitem(i),)
Next
End Sub
}
Form 100,50
LatinSquare 5, 2, True
LatinSquare 16
 
 
Output:
A latin square of 5 by 5
 4 5 3 1 2
 5 4 2 3 1
 2 1 5 4 3
 1 3 4 2 5
 3 2 1 5 4
A latin square of 5 by 5
 4 3 5 1 2
 2 4 3 5 1
 1 2 4 3 5
 5 1 2 4 3
 3 5 1 2 4
A latin square of 16 by 16
12 14 5 16 1 2 7 15 9 11 10 8 13 3 6 4
 3 13 16 12 7 4 1 11 5 6 15 2 8 14 10 9
 13 2 8 3 4 12 5 9 14 7 16 10 6 1 15 11
 8 3 13 9 2 10 16 1 15 14 5 4 11 7 12 6
 4 12 2 7 5 3 6 10 1 9 11 16 14 8 13 15
 16 8 3 4 14 6 13 7 11 10 9 15 1 12 2 5
 15 4 14 1 16 8 2 13 6 12 7 9 10 11 5 3
 11 16 12 10 15 9 4 5 7 1 8 6 3 13 14 2
 10 15 4 5 12 16 3 6 8 13 1 11 7 2 9 14
 9 11 15 8 3 1 14 12 13 4 6 5 2 16 7 10
 7 10 11 13 9 14 15 4 3 5 2 12 16 6 1 8
 6 7 10 2 8 13 9 16 12 15 14 3 5 4 11 1
 5 6 1 14 13 11 8 2 10 3 12 7 15 9 4 16
 2 5 6 15 11 7 12 14 4 8 3 1 9 10 16 13
 1 9 7 11 6 15 10 8 2 16 13 14 4 5 3 12
 14 1 9 6 10 5 11 3 16 2 4 13 12 15 8 7

Perl 6[edit]

Works with: Rakudo version 2019.03
Translation of: Python
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 5, 3, 9;
 
# Or, if you'd prefer:
display random latin-square, :size($_) for 12, 2, 1;
Sample output:
 V   Z   M   J   U 
 Z   M   U   V   J 
 U   J   V   M   Z 
 J   V   Z   U   M 
 M   U   J   Z   V 
   
 B   H   K   U   D 
 H   D   U   B   K 
 K   U   H   D   B 
 U   B   D   K   H 
 D   K   B   H   U 
   
 I   P   Y 
 P   Y   I 
 Y   I   P 
   
 Y   J   K   E   Z   B   I   W   H 
 E   Y   B   W   K   H   J   Z   I 
 B   K   Y   H   J   E   Z   I   W 
 I   H   W   J   E   Z   B   Y   K 
 J   I   Z   Y   W   K   H   E   B 
 W   E   H   Z   B   I   Y   K   J 
 H   B   E   I   Y   W   K   J   Z 
 K   Z   J   B   I   Y   W   H   E 
 Z   W   I   K   H   J   E   B   Y 
   
 L   Q   E   M   A   T   Z   C   N   Y   R   D 
 Q   R   Y   L   N   D   C   E   M   T   A   Z 
 E   Y   M   C   D   Q   A   N   Z   L   T   R 
 M   L   C   N   R   Y   D   Z   A   E   Q   T 
 N   M   Z   A   Q   E   T   D   R   C   L   Y 
 T   D   Q   Y   C   A   M   L   E   R   Z   N 
 R   A   T   Q   M   Z   E   Y   L   D   N   C 
 D   Z   R   T   E   N   L   Q   Y   A   C   M 
 Y   T   L   E   Z   R   N   M   C   Q   D   A 
 A   N   D   R   L   C   Y   T   Q   Z   M   E 
 Z   C   A   D   Y   M   Q   R   T   N   E   L 
 C   E   N   Z   T   L   R   A   D   M   Y   Q 
   
 Y   G 
 G   Y 
   
 I

Python[edit]

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()
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

REXX[edit]

This REXX version produces a randomized Latin square similar to the   Julia   program.

The symbols could be any characters (except those that contain a blank),   but the numbers from   0 ──► N-1   are used.

/*REXX program generates and displays a randomized Latin square.                        */
parse arg N seed . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 5 /*Not specified? Then use the default.*/
if datatype(seed, 'W') then call random ,,seed /*Seed numeric? Then use it for seed.*/
w= length(N - 1) /*get the length of the largest number.*/
$= /*initialize $ string to null. */
do i=0 for N; $= $ right(i, w, '_') /*build a string of numbers (from zero)*/
end /*i*/ /* [↑] $ string is (so far) in order.*/
z= /*Z: will be the 1st row of the square*/
do N;  ?= random(1,words($)) /*gen a random number from the $ string*/
z= z word($, ?); $= delword($, ?, 1) /*add the number to string; del from $.*/
end /*r*/
zz= z||z /*build a double-length string of Z. */
do j=1 for N /* [↓] display rows of random Latin sq*/
say translate(subword(zz, j, N), , '_') /*translate leading underbar to blank. */
end /*j*/ /*stick a fork in it, we're all done. */
output   for the 1st run when using the default inputs:
4 1 3 0 2
1 3 0 2 4
3 0 2 4 1
0 2 4 1 3
2 4 1 3 0
output   for the 2nd run when using the default inputs:
2 1 0 4 3
1 0 4 3 2
0 4 3 2 1
4 3 2 1 0
3 2 1 0 4

Ruby[edit]

This crude algorithm works fine up to a square size of 10; higher values take too much time and memory. It creates an array of all possible permutations, picks a random one as first row an weeds out all permutations which cannot appear in the remaining square. Repeat picking and weeding until there is a square.

N = 5
 
def generate_square
perms = (1..N).to_a.permutation(N).to_a.shuffle
square = []
N.times do
square << perms.pop
perms.reject!{|perm| perm.zip(square.last).any?{|el1, el2| el1 == el2} }
end
square
end
 
def print_square(square)
cell_size = N.digits.size + 1
strings = square.map!{|row| row.map!{|el| el.to_s.rjust(cell_size)}.join }
puts strings, "\n"
end
 
2.times{print_square( generate_square)}
 
Output:

3 4 2 1 5
2 3 4 5 1
1 2 5 3 4
5 1 3 4 2
4 5 1 2 3
1 2 5 4 3
2 3 4 1 5
5 4 2 3 1
3 5 1 2 4
4 1 3 5 2

zkl[edit]

fcn randomLatinSquare(n,symbols=[1..]){  //--> list of lists
if(n<=0) return(T);
square,syms := List(), symbols.walker().walk(n);
do(n){ syms=syms.copy(); square.append(syms.append(syms.pop(0))) }
// shuffle rows, transpose & shuffle columns
T.zip(square.shuffle().xplode()).shuffle();
}
fcn rls2String(square){ square.apply("concat"," ").concat("\n") }
foreach n in (T(1,2,5)){ randomLatinSquare(n) : rls2String(_).println("\n") }
randomLatinSquare(5, ["A".."Z"])  : rls2String(_).println("\n");
randomLatinSquare(10,"[email protected]#$%^&*()") : rls2String(_).println("\n");
Output:
1

1 2
2 1

3 1 4 5 2
4 2 5 1 3
1 4 2 3 5
5 3 1 2 4
2 5 3 4 1

E D A B C
D C E A B
B A C D E
A E B C D
C B D E A

& % # ! * @ ) $ ( ^
@ ) * ^ # & % ( $ !
( & % # ) $ @ ^ ! *
! ( & % @ ^ $ * # )
% # ! ( ^ ) * @ & $
^ $ @ ) & ! ( # * %
# ! ( & $ * ^ ) % @
$ @ ) * % ( & ! ^ #
) * ^ $ ! % # & @ (
* ^ $ @ ( # ! % ) &