Random Latin squares

Random Latin squares
You are encouraged to solve this task according to the task description, using any language you may know.

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

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

• Latin square
• OEIS A002860

Factor

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.

<lang factor>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 ] bi@ :> ( n1 n2 )
   n1 n2 [ sq ] bi@ 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 ] bi@
   "Koscielny product of previous squares:" print
   koscielny-product simple-table. ;

MAIN: random-latin-squares</lang>

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

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. <lang go>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

}</lang>

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

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

M2000 Interpreter

Easy Way

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.

<lang M2000 Interpreter> Module FastLatinSquare { n=5 For k=1 To 2 latin() Next n=40 latin() Sub latin() Local i,a, a(1 To n) 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) For i=1 To n*10 Shiftback random(2, n) Next i For i=1 To n Data number b=[] ' move stack To b, leave empty stack a(stackitem(a, 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 </lang>

Hard Way

for 5x5 need some miliseconds

for 16X16 need 56 seconds

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

<lang M2000 Interpreter> 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

</lang>

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

Works with: Rakudo version 2019.03

Translation of: Python

<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, }

1. The Task

1. Default size 5

display random latin-square;

1. Specified size

display random :size($_), latin-square for 5, 3, 9;

1. Or, if you'd prefer:

display random latin-square, :size($_) for 12, 2, 1;</lang>

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

<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

Ruby

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. <lang ruby>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)} </lang>

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

<lang zkl>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") }</lang> <lang zkl>foreach n in (T(1,2,5)){ randomLatinSquare(n) : rls2String(_).println("\n") } randomLatinSquare(5, ["A".."Z"])  : rls2String(_).println("\n"); randomLatinSquare(10,"!@#$%^&*()") : rls2String(_).println("\n");</lang>

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

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