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
- Create 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
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), 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 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 </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
<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 5, 3, 9;
- 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 31 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 & % # ! * @ ) $ ( ^ @ ) * ^ # & % ( $ ! ( & % # ) $ @ ^ ! * ! ( & % @ ^ $ * # ) % # ! ( ^ ) * @ & $ ^ $ @ ) & ! ( # * % # ! ( & $ * ^ ) % @ $ @ ) * % ( & ! ^ # ) * ^ $ ! % # & @ ( * ^ $ @ ( # ! % ) &