Random Latin squares: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Bleh, missed the requirement for specifically _two_ size 5 squares, adjusted and regenerated) |
(Added Go) |
||
Line 19: | Line 19: | ||
;Reference: |
;Reference: |
||
* [[wp:Latin_square|Latin square]] |
* [[wp:Latin_square|Latin square]] |
||
=={{header|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) { |
|||
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> |
|||
{{out}} |
|||
<pre> |
|||
[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] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 68: | Line 173: | ||
0 1 4 2 3 |
0 1 4 2 3 |
||
</pre> |
</pre> |
||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 17:08, 9 June 2019
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
- Generate a function/routine/procedure/method/... that given
n
generates 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
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) {
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