Random Latin squares: Difference between revisions
m (Better English.) |
(Promote to full task status.) |
||
| Line 1: | Line 1: | ||
{{ |
{{task}} |
||
A Latin square of size <code>n</code> is an arrangement of <code>n</code> symbols in an <code>n-by-n</code> square in such a way that each row and column has each symbol appearing exactly once.<br> |
A Latin square of size <code>n</code> is an arrangement of <code>n</code> symbols in an <code>n-by-n</code> square in such a way that each row and column has each symbol appearing exactly once.<br> |
||
Revision as of 16:08, 10 June 2019
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
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
zkl
<lang zkl>fcn randomLatinSquare(n,symbols=[1..]){
if(n<=0) return(T); symbols.walker().walk(n).copy() : _rls(_) : T.zip(_.shuffle().xplode()).shuffle()
} fcn _rls(symbols){ // <-->mutable list of lists
n:=symbols.len();
if(n==1) return(List(symbols)); // (1) --> ( (1) )
z,sym := (0).random(n), symbols[z];
symbols.del(z);
square:=_rls(symbols);
square.append(square[0].copy());
foreach i in (n){ square[i].insert(i,sym) }
square
} fcn m2String(matrix){ matrix.apply("concat"," ").concat("\n") }</lang> <lang zkl>foreach n in (T(1,2,5)){ randomLatinSquare(n) : m2String(_).println("\n") } randomLatinSquare(5,["A".."Z"]) : m2String(_).println("\n"); randomLatinSquare(10,"!@#$%^&*()") : m2String(_).println("\n");</lang>
- Output:
1 1 2 2 1 5 1 2 3 4 1 4 5 2 3 3 2 4 1 5 4 3 1 5 2 2 5 3 4 1 C D A E B B C D A E E B C D A D A E B C A E B C D ) & * # ^ @ ( % $ ! @ ( % ! # $ * ) ^ & & $ # ) % ( ^ ! * @ * # & $ @ % ! ( ) ^ % ! ( ^ $ ) & * @ # $ * ) & ! ^ % @ # ( ( ^ ! @ ) * # & % $ ! @ ^ % * & $ # ( ) ^ % @ ( & # ) $ ! * # ) $ * ( ! @ ^ & %