Random Latin squares: Difference between revisions
added RPL
(added RPL) |
|||
| (26 intermediate revisions by 9 users not shown) | |||
Line 2:
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>
For the purposes of this task, a random Latin square of size <code>n</code> is a Latin square constructed or generated by a probabilistic procedure such that the probability of any particular Latin square of size <code>n</code> being produced is non-zero.
;Example n=4 randomised Latin square:
Line 15:
;Note:
Strict ''
;Related tasks:
* [[Latin Squares in reduced form/Randomizing using Jacobson and Matthews’ Technique]]
* [[Latin Squares in reduced form]]
;Reference:
Line 25 ⟶ 29:
{{trans|Python}}
<
assert(matrix.len == matrix[0].len)
V r = [[0] * matrix.len] * matrix.len
Line 70 ⟶ 74:
print(square.map(row -> row.join(‘ ’)).join("\n"))
_check(square)
print()</
{{out}}
Line 96 ⟶ 100:
=={{header|Action!}}==
<
DEFINE DIMENSION="5"
Line 219 ⟶ 223:
PutE()
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Random_Latin_squares.png Screenshot from Atari 8-bit computer]
Line 234 ⟶ 238:
1 2 0 3 4
0 4 2 1 3
</pre>
=={{header|ALGOL 68}}==
{{Trans|Nim}}
Uses the Knuth Shuffle routine from the Algol 68 sample in the Knuth Shuffle task - modified to shuffle a row in a CHAR matrix.
<br>
Generating largish squares can take some time...
<syntaxhighlight lang="algol68">
BEGIN # generate random latin squares #
# Knuth Shuffle routine from the Knuth Shuffle Task #
# modified to shufflw a row of a [,]CHAR array #
PROC knuth shuffle = (REF[,]CHAR a, INT row)VOID:
(
PROC between = (INT a, b)INT :
(
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
);
FOR i FROM LWB a TO UPB a DO
INT j = between(LWB a, UPB a);
CHAR t = a[row, i];
a[row, i] := a[row, j];
a[row, j] := t
OD
);
# generates a random latin square #
PROC latin square = ( INT n )[,]CHAR:
BEGIN
[ 1 : n ]CHAR letters;
[ 1 : n, 1 : n ]CHAR result;
FOR col TO n DO
letters[ col ] := REPR ( ABS "A" + ( col - 1 ) )
OD;
FOR row TO n DO
result[ row, : ] := letters
OD;
knuth shuffle( result, 1 );
FOR row FROM 2 TO n - 1 DO
BOOL ok := FALSE;
WHILE
knuth shuffle( result, row );
BOOL all different := TRUE;
FOR prev TO row - 1 WHILE all different DO
FOR col TO n
WHILE all different :=
result[ row, col ] /= result[ prev, col ]
DO SKIP OD
OD;
NOT all different
DO SKIP OD
OD;
# the final row, there is only one possibility for each column #
FOR col TO n DO
[ 1 : n ]CHAR free := letters;
FOR row TO n - 1 DO
free[ ( ABS result[ row, col ] - ABS "A" ) + 1 ] := REPR 0
OD;
BOOL found := FALSE;
FOR row FROM 1 LWB result TO 1 UPB result WHILE NOT found DO
IF free[ row ] /= REPR 0 THEN
found := TRUE;
result[ n, col ] := free[ row ]
FI
OD
OD;
result
END # latin suare # ;
# prints a latin square #
PROC print square = ( [,]CHAR square )VOID:
FOR row FROM 1 LWB square TO 1 UPB square DO
IF 2 LWB square <= 2 UPB square THEN
print( ( square[ row, 2 LWB square ] ) );
FOR col FROM 2 LWB square + 1 TO 2 UPB square DO
print( ( " ", square[ row, col ] ) )
OD;
print( ( newline ) )
FI
OD # print square # ;
next random;
print square( latin square( 5 ) );
print( ( newline ) );
print square( latin square( 5 ) );
print( ( newline ) );
print square( latin square( 10 ) )
END
</syntaxhighlight>
{{out}}
<pre>
A C D B E
C A B E D
D E A C B
E B C D A
B D E A C
A B E C D
B E D A C
E C B D A
D A C E B
C D A B E
A C D J F G I B E H
D F H G E A B J C I
H E C I B J A F G D
B I G A C H J D F E
E J I F H C D G B A
I D B C G F H E A J
C H F B J I E A D G
G B J D A E F I H C
J G A E D B C H I F
F A E H I D G C J B
</pre>
=={{header|Arturo}}==
<
square: new []
variants: shuffle permutate 0..n-1
Line 261 ⟶ 379:
print row
print "---------"
]</
{{out}}
Line 279 ⟶ 397:
=={{header|C}}==
{{trans|C++}}
<
#include <stdio.h>
#include <stdlib.h>
Line 396 ⟶ 514:
return 0;
}</
{{out}}
<pre>[1, 4, 3, 0, 2]
Line 423 ⟶ 541:
=={{header|C++}}==
{{trans|Java}}
<
#include <chrono>
#include <iostream>
Line 516 ⟶ 634:
latinSquare(10);
return 0;
}</
{{out}}
<pre>[4, 3, 1, 2, 0]
Line 543 ⟶ 661:
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<
using System.Collections.Generic;
Line 647 ⟶ 765:
}
}
}</
{{out}}
<pre>[3, 0, 1, 4, 2]
Line 674 ⟶ 792:
=={{header|D}}==
{{trans|C#}}
<
import std.random;
import std.stdio;
Line 746 ⟶ 864:
latinSquare(10);
}</
{{out}}
<pre>[2, 4, 3, 1, 0]
Line 770 ⟶ 888:
[7, 0, 6, 2, 5, 4, 3, 8, 1, 9]
[9, 7, 5, 4, 1, 3, 0, 6, 2, 8]</pre>
=={{header|EasyLang}}==
{{trans|Kotlin}}
<syntaxhighlight>
proc shuffle . a[] .
for i = len a[] downto 2
r = randint i
swap a[r] a[i]
.
.
proc prsquare . lat[][] .
n = len lat[][]
for i to n
for j to n
write lat[i][j] & " "
.
print ""
.
print ""
.
proc square n . .
for i to n
lat[][] &= [ ]
for j to n
lat[i][] &= j
.
.
shuffle lat[1][]
for i = 2 to n - 1
repeat
shuffle lat[i][]
for k to i - 1
for j to n
if lat[k][j] = lat[i][j]
break 2
.
.
.
until k = i
.
.
len used0[] n
for j to n
used[] = used0[]
for i to n - 1
used[lat[i][j]] = 1
.
for k to n
if used[k] = 0
lat[n][j] = k
break 1
.
.
.
prsquare lat[][]
.
square 5
square 5
</syntaxhighlight>
{{out}}
<pre>
1 5 4 2 3
3 4 2 1 5
2 1 5 3 4
5 3 1 4 2
4 2 3 5 1
3 5 1 4 2
2 1 4 3 5
5 2 3 1 4
4 3 2 5 1
1 4 5 2 3
</pre>
=={{header|F_Sharp|F#}}==
This solution uses functions from [[Factorial_base_numbers_indexing_permutations_of_a_collection#F.23]] and [[Latin_Squares_in_reduced_form#F.23]].
<
// Generate 2 Random Latin Squares of order 5. Nigel Galloway: July 136th., 2019
let N=let N=System.Random() in (fun n->N.Next(n))
let rc()=let β=lN2p [|0;N 4;N 3;N 2|] [|0..4|] in Seq.item (N 56) (normLS 5) |> List.map(lN2p [|N 5;N 4;N 3;N 2|]) |> List.permute(fun n->β.[n]) |> List.iter(printfn "%A")
rc(); printfn ""; rc()
</syntaxhighlight>
{{out}}
<pre>
Line 819 ⟶ 1,011:
=={{header|Factor}}==
A brute force method for generating
<
prettyprint random sequences sets ;
IN: rosetta-code.random-latin-squares
Line 830 ⟶ 1,022:
: random-latin-squares ( -- ) [ 5 ls simple-table. nl ] twice ;
MAIN: random-latin-squares</
{{out}}
<pre>
Line 845 ⟶ 1,037:
3 1 2 4 0
</pre>
=={{header|FreeBASIC}}==
{{trans|Wren}}
====Restarting Row method====
<syntaxhighlight lang="vbnet">Randomize Timer
Sub printSquare(latin() As Integer, n As Integer)
For i As Integer = 0 To n - 1
Print "[";
For j As Integer = 0 To n - 1
Print latin(i, j); ",";
Next j
Print Chr(8); " ]"
Next i
Print
End Sub
Sub latinSquare(n As Integer)
Dim As Integer i, j, k
If n <= 0 Then
Print "[]"
Exit Sub
End If
Dim latin(n - 1, n - 1) As Integer
For i = 0 To n - 1
For j = 0 To n - 1
latin(i, j) = j
Next j
Next i
' first row
For i = 0 To n - 1
Dim j As Integer = Int(Rnd * n)
Swap latin(0, i), latin(0, j)
Next i
' middle row(s)
For i = 1 To n - 2
Dim shuffled As Integer = 0
While shuffled = 0
For j = 0 To n - 1
Dim k As Integer = Int(Rnd * n)
Swap latin(i, j), latin(i, k)
Next j
shuffled = 1
For k As Integer = 0 To i - 1
For j = 0 To n - 1
If latin(k, j) = latin(i, j) Then
shuffled = 0
Exit For
End If
Next j
If shuffled = 0 Then Exit For
Next k
Wend
Next i
' last row
For j = 0 To n - 1
Dim used(n - 1) As Integer
For i = 0 To n - 2
used(latin(i, j)) = 1
Next i
For k = 0 To n - 1
If used(k) = 0 Then
latin(n - 1, j) = k
Exit For
End If
Next k
Next j
printSquare(latin(), n)
End Sub
latinSquare(5)
latinSquare(5)
latinSquare(10) ' for good measure
Sleep</syntaxhighlight>
=={{header|Go}}==
===Restarting Row method===
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 known as the 'Restarting Row' method (see Talk page). However, whilst easy to understand, this method does not produce uniformly random squares.
<
import (
Line 928 ⟶ 1,199:
latinSquare(5)
latinSquare(10) // for good measure
}</
{{out}}
Line 959 ⟶ 1,230:
===Latin Squares in Reduced Form method===
Unlike the "Restarting Row" method, this method does produce uniformly random Latin squares for n <= 6 (see Talk page) but is more involved and therefore slower. It reuses some (suitably adjusted) code from the [https://rosettacode.org/wiki/Latin_Squares_in_reduced_form#Go Latin Squares in Reduced Form] and [https://rosettacode.org/wiki/Permutations#non-recursive.2C_lexicographical_order Permutations] tasks.
<
import (
Line 1,211 ⟶ 1,482:
fmt.Println("\nA randomly generated latin square of order 6 is:\n")
generateLatinSquares(6, 1, 1)
}</
{{out}}
Line 1,255 ⟶ 1,526:
given first row and first column.
<
latinSquare :: Eq a => [a] -> [a] -> [[a]]
Line 1,282 ⟶ 1,553:
putStrLn $
unlines $
unwords . map show <$> tbl</
<pre>λ> printTable $ latinSquare [1,2,3,4,5] [1,3,2,5,4]
Line 1,294 ⟶ 1,565:
the deterministic algorithm.
<
randomLatinSquare set = do
r <- randomPermutation set
c <- randomPermutation (tail r)
return $ latinSquare r (head r:c)</
For examples a naive linear congruent method in a State monad is used.
<
type Random a = State Int a
Line 1,322 ⟶ 1,593:
randomSample :: [a] -> Random a
randomSample lst = (lst !!) <$> random (length lst)</
<pre>λ> printTable $ randomLatinSquare [0..4] `evalState` 42
Line 1,345 ⟶ 1,616:
=={{header|J}}==
<
s=. ?~ y NB. "deal" y unique integers from 0 to y
for_ijk. i.<:y do.
Line 1,356 ⟶ 1,627:
end.
)
</syntaxhighlight>
{{out}}
<pre> rls 5
Line 1,373 ⟶ 1,644:
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.Collections;
import java.util.Iterator;
Line 1,458 ⟶ 1,729:
latinSquare(10);
}
}</
{{out}}
<pre>[1, 3, 4, 0, 2]
Line 1,484 ⟶ 1,755:
=={{header|Javascript}}==
<
class Latin {
constructor(size = 3) {
Line 1,537 ⟶ 1,808:
}
new Latin(5);
</syntaxhighlight>
{{out}}
<pre>
Line 1,551 ⟶ 1,822:
1 2 3 5 4
2 3 5 4 1
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq.'''
This entry presents two jq programs for generating Latin Squares of order n
(LS(n)) in accordance with the requirements.
The first program uses a "brute-force" algorithm (with simple optimizations) to
generate Latin Squares of order n as though drawing with
replacement from the population of all such Latin Squares.
The chi-squared statistics show good agreement
with the theoretical uniformity.
The second program uses a much faster algorithm for generating Latin Squares
in accordance with the requirements, but with bias away from
uniformity, as also illustrated by chi-squared statistics.
Both algorithms use /dev/random as a source of entropy. They also
both use the Knuth shuffle to generate the first row, and rely on
backtracking using the jq idiom:
`first( repeat( _) )`
The first algorithm incrementally adds rows, backtracking to the
point immediately after the selection of the first row. For n larger
than about 4, this algorithm is quite slow, though in a fairly predictable way.
The second algorithm incrementally adds cells, backtracking to the
last cell. It is much faster but the running time can be quite
variable, as suggested by this table:
<pre>
n Typical range of u+s times on 3GHz machine
10 0.11 to 0.14 s
15 0.15 to 0.21 s
20 0.36 to 0.94 s
30 0.5 to 29 seconds
40 80 seconds to 21 minutes
45 8 to 39 minutes
</pre>
An interesting variant of the second algorithm can be obtained by
a trivial modification of just one line (see the comment with "n.b."):
backtracking to the last full row is slightly faster while maintaining
randomness, at the cost of a greater departure from uniform
randomness, as confirmed by these two runs using the same `stats`
function as defined in the first program.
<pre>
# Using `ext` (i.e., backtrack to point after selection of first row)
Number of LS(4): 5760
Of 576 possibilities, only 575 were generated.
Chi-squared statistic (df=575): 2128.6
# u+s 5.5s
# Using `extend` (i.e. backtrack to point of most recent row extension - faster but more biased)
Number of LS(4): 5760
All 576 possibilities have been generated.
Chi-squared statistic (df=575): 3055.8
# u+s 4.7s
</pre>
<syntaxhighlight lang=sh>
#!/bin/bash
< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr -f random-latin-squares.jq
</syntaxhighlight>
=== Common Functions ===
<syntaxhighlight lang=sh>
'''Generic Utility Functions'''
# For inclusion using jq's `include` directive:
# Output: a PRN in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# If the input array is not rectangular, let nulls fall where they may
def column($j):
[.[] | .[$j]];
# Emit a stream of [value, frequency] pairs
def histogram(stream):
reduce stream as $s ({};
($s|type) as $t
| (if $t == "string" then $s else ($s|tojson) end) as $y
| .[$t][$y][0] = $s
| .[$t][$y][1] += 1 )
| .[][] ;
def ss(s): reduce s as $x (0; . + ($x * $x));
def chiSquared($expected): ss( .[] - $expected ) / $expected;
</syntaxhighlight>
===Latin Squares selected at random uniformly===
<syntaxhighlight lang=sh>
# Include the utilities e.g. by
# include "random-latin-squares.utilities" {search: "."};
# Determine orthogonality of two arrays, confining attention
# to the first $n elements in each:
def orthogonal($a; $b; $n):
first( (range(0; $n) | if $a[.] == $b[.] then 0 else empty end) // 1) | . == 1;
# Are the two arrays orthogonal up to the length of the shorter?
def orthogonal($a; $b):
([$a, $b | length] | min) as $min
| orthogonal($a; $b; $min);
# Is row $i orthogonal to all the previous rows?
def orthogonal($i):
. as $in
| .[$i] as $row
| all(range(0;$i); orthogonal($row; $in[.]));
# verify columnwise orthogonality
def columnwise:
length as $n
| transpose as $t
| all( range(1;$n); . as $i | $t | orthogonal($i)) ;
def addLast:
(.[0] | length) as $n
| [range(0; $n)] as $range
| [range(0; $n) as $i
| ($range - column($i))[0] ] as $last
| . + [$last] ;
# input: an array being a permutation of [range(0;$n)] for some $n
# output: a Latin Square selected at random from all the candidates
def extend:
(.[0] | length) as $n
| if length >= $n then .
elif length == $n - 1 then addLast
else ([range(0; $n)] | knuthShuffle) as $row
| (. + [$row] )
| if orthogonal(length - 1) and columnwise then extend else empty end
end ;
# Generate a Latin Square.
# The input should be an integer specifying its size.
def latinSquare:
. as $n
| if $n <= 0 then []
else
[ [range(0; $n)] | knuthShuffle]
| first(repeat(extend))
# | (if columnwise then . else debug end) # internal check
end ;
# If the input is a positive integer, $n, generate and print an $n x $n Latin Square.
# If it is not number, echo it.
def printLatinSquare:
if type == "number"
then latinSquare
| .[] | map(lpad(3)) | join(" ")
else .
end;
# $order should be in 1 .. 5 inclusive
# If $n is null, then use 10 * $counts[$order]
def stats($order; $n):
# table of counts:
[0,1,2,12,576,161280] as $counts
| $counts[$order] as $possibilities
| (if $n then $n else 10 * $possibilities end) as $n
| reduce range(0;$n) as $i ({};
($order|latinSquare|flatten|join("")) as $row
| .[$row] += 1)
| # ([histogram(.[])] | sort[] | join(" ")),
"Number of LS(\($order)): \($n)",
(if length == $possibilities
then "All \($possibilities) possibilities have been generated."
else "Of \($possibilities) possibilities, only \(length) were generated."
end),
"Chi-squared statistic (df=\($possibilities-1)): \( [.[]] | chiSquared( $n / $possibilities))";
stats(3;null), "",
stats(4;5760), ""
stats(4;5760)
</syntaxhighlight>
{{output}}
<pre>
Number of LS(3): 120
All 12 possibilities have been generated.
Chi-squared statistic (df=11): 18.8
Number of LS(4): 5760
All 576 possibilities have been generated.
Chi-squared statistic (df=575): 572.2
Number of LS(4): 5760
All 576 possibilities have been generated.
Chi-squared statistic (df=575): 517.2
</pre>
=== Random Latin Squares ===
This is the (much) faster program that meets the task
requirements while deviating from uniform randomness
as suggested by the Chi-squared statistics presented in the preamble.
<syntaxhighlight lang=sh>
# Include the utilities e.g. by
# include "random-latin-squares.utilities" {search: "."};
# Select an element at random from [range(0;$n)] - column($j)
def candidate($j):
(.[0] | length) as $n
| [range(0;$n)] - column($j)
| .[length|prn];
# Input: the first row or rows of a Latin Square
def extend:
# The input to ext should be several rows of a Latin Square
# optionally followed by a candidate for an additional row.
def ext:
.[0] as $first
| length as $length
| ($first|length) as $n
| .[-1] as $last
| if ($last|length) < $n # then extend the last row
then ( ([range(0;$n)] - column($last|length)) - $last) as $candidates
| .[:$length-1] as $good
| ($candidates|length) as $cl
# if we can complete the row, then there is no need for another backtrack point!
| if $cl == 1 and ($last|length) == $n - 1
then ($good + [ $last + $candidates]) | ext # n.b. or use `extend` to speed things up at the cost of more bias
else
if $cl == 1 then ($good + [ $last + $candidates]) | ext
elif $cl == 0
then empty
else ($candidates[$cl | prn] as $add
| ($good + [$last + [$add]]) | ext)
end
end
elif length < $n then ((. + [[candidate(0)]]) | ext)
else .
end;
# If at first you do not succeed ...
first( repeat( ext ));
# Generate a Latin Square.
# The input should be an integer specifying its size.
def latinSquare:
. as $n
| if $n <= 0 then []
else
[ [range(0; $n)] | knuthShuffle]
| extend
end ;
# If the input is a positive integer, $n, generate and print an $n x $n Latin Square.
# Otherwise, simply echo it.
def printLatinSquare:
if type == "number"
then latinSquare
| .[] | map(lpad(3)) | join(" ")
else .
end;
"Five", 5, "\nFive", 5, "\nTen", 10, "\nForty", 40
| printLatinSquare
'
</syntaxhighlight>
{{output}}
<pre style="font-size: xx-small">
Five
2 1 3 4 0
1 4 0 2 3
4 3 2 0 1
3 0 4 1 2
0 2 1 3 4
Five
1 0 2 3 4
4 3 0 1 2
0 4 3 2 1
2 1 4 0 3
3 2 1 4 0
Ten
0 4 9 1 5 3 8 7 2 6
5 8 7 9 3 6 0 2 4 1
8 7 2 6 0 1 4 5 3 9
9 3 1 2 7 4 5 6 0 8
7 2 5 4 6 0 9 8 1 3
6 9 0 8 4 5 1 3 7 2
3 0 8 7 9 2 6 1 5 4
4 1 6 3 2 8 7 0 9 5
1 5 3 0 8 9 2 4 6 7
2 6 4 5 1 7 3 9 8 0
Forty
30 29 36 1 37 23 27 33 22 32 38 20 5 13 25 35 16 18 19 24 11 6 4 12 3 10 21 26 34 39 14 28 31 2 8 7 9 17 0 15
16 30 21 32 24 6 25 17 35 12 26 10 19 33 18 31 29 34 4 13 15 28 0 3 5 11 9 23 14 2 20 38 37 8 39 27 1 22 36 7
21 4 27 11 5 12 9 13 30 20 3 36 31 0 24 16 28 1 8 33 38 2 23 22 29 32 18 34 6 7 15 17 25 26 10 35 19 14 39 37
2 13 18 36 15 19 17 32 27 24 9 3 26 21 1 0 10 39 38 16 20 14 34 6 28 22 12 7 11 8 5 23 33 37 30 4 29 31 25 35
35 39 10 0 3 15 1 37 7 4 6 2 27 9 29 38 34 16 33 28 32 30 24 14 18 23 31 12 19 17 21 36 8 13 20 25 22 5 11 26
13 27 34 25 17 1 21 5 23 39 2 8 0 38 22 7 32 9 29 26 18 4 36 19 30 16 14 20 31 28 3 6 35 11 15 12 33 10 37 24
36 31 26 3 25 2 11 38 13 18 24 35 17 10 20 1 7 15 6 19 22 0 12 32 33 27 4 30 37 9 8 29 14 28 34 39 23 16 5 21
26 25 35 31 6 34 5 8 11 19 30 1 20 15 33 10 23 38 0 21 37 29 2 39 14 17 28 27 32 18 24 7 12 3 36 13 4 9 22 16
18 14 4 30 33 38 8 2 1 28 21 27 13 36 37 22 15 3 20 31 7 25 6 0 12 29 26 32 17 35 23 34 11 9 19 5 16 24 10 39
14 21 5 34 8 29 0 10 20 9 28 39 35 4 17 30 26 11 25 38 16 19 31 15 32 1 6 24 13 37 7 27 36 33 23 18 2 12 3 22
15 28 24 2 34 7 3 35 29 30 0 4 38 25 6 27 11 12 17 37 26 20 21 5 1 14 10 8 33 16 36 9 13 32 22 19 39 18 31 23
38 3 23 7 39 37 13 20 21 25 33 5 6 32 14 4 8 35 12 9 24 17 11 34 27 36 16 22 26 0 31 18 2 29 1 15 28 19 30 10
11 19 30 5 31 18 10 21 6 23 34 33 4 12 2 14 37 22 39 1 25 8 16 38 24 28 36 13 3 27 29 26 32 35 7 20 0 15 9 17
0 9 12 20 16 30 38 11 18 14 4 17 10 7 19 36 3 27 37 35 29 22 26 28 21 8 13 39 23 33 34 31 24 6 2 32 25 1 15 5
29 2 16 18 35 17 37 25 10 27 39 31 3 6 23 34 9 19 30 4 13 38 1 21 8 0 22 5 36 24 12 33 28 15 26 14 11 32 7 20
22 35 29 38 23 8 7 6 9 36 14 0 18 34 27 3 12 33 5 39 21 11 30 31 10 26 15 17 1 4 37 16 20 19 13 24 32 2 28 25
32 16 25 4 26 22 36 1 28 3 27 7 14 19 39 5 33 21 9 2 23 31 13 20 11 37 30 0 15 34 35 10 17 24 29 38 18 8 12 6
33 20 32 13 30 21 35 7 24 2 19 16 11 37 4 23 14 31 36 15 1 39 22 9 25 38 27 6 0 26 10 8 29 5 17 3 34 28 18 12
5 0 28 26 22 39 30 27 33 31 12 24 21 35 11 20 4 32 34 8 9 16 15 17 19 25 3 1 10 6 18 2 38 7 14 37 13 29 23 36
25 5 17 37 11 13 4 18 36 34 23 32 9 20 12 19 21 2 3 0 30 10 35 26 38 24 39 28 22 15 16 1 27 14 31 6 8 7 33 29
10 32 1 17 12 31 39 30 15 26 25 11 33 27 13 29 6 37 2 3 8 24 18 4 7 21 35 16 20 5 9 19 34 23 38 22 36 0 14 28
31 37 33 27 4 20 14 9 34 29 32 26 22 30 28 12 5 25 24 17 10 7 39 11 23 2 1 36 18 38 13 35 21 16 0 8 15 6 19 3
4 34 11 15 27 33 19 14 37 0 8 29 28 5 3 18 2 10 31 12 39 23 20 35 13 30 24 21 25 1 6 22 26 17 16 36 7 38 32 9
1 38 14 21 7 4 34 16 2 22 13 12 29 31 15 28 25 36 32 10 27 3 37 33 17 5 0 9 30 23 11 20 39 18 6 26 24 35 8 19
28 26 20 10 14 35 29 4 16 8 37 38 7 17 9 32 19 6 23 30 5 36 27 2 15 13 25 11 12 22 0 39 3 34 24 33 31 21 1 18
20 10 6 29 21 24 32 19 39 16 31 15 36 23 34 37 17 13 1 25 14 18 9 27 0 7 8 38 35 12 30 5 4 22 3 28 26 11 2 33
24 7 9 8 18 5 26 0 19 15 1 30 2 22 36 21 35 17 27 29 3 33 38 10 4 39 11 25 16 20 28 12 23 31 32 34 37 13 6 14
37 33 3 19 10 25 20 26 17 13 11 34 23 1 30 8 22 5 28 14 2 12 7 18 36 15 29 35 21 32 27 4 16 38 9 0 6 39 24 31
39 1 31 9 29 14 15 3 26 17 36 25 30 11 38 24 27 28 18 32 6 5 33 37 2 19 7 10 4 13 22 21 0 20 12 23 35 34 16 8
34 17 15 24 28 16 6 22 8 7 5 14 25 29 35 2 30 26 11 27 12 1 19 36 39 20 23 4 9 21 38 32 18 10 37 31 3 33 13 0
12 24 22 39 19 28 18 15 32 33 7 23 16 26 8 11 36 14 13 34 0 9 29 30 6 35 2 31 38 25 4 3 5 27 21 10 17 37 20 1
8 23 7 28 9 27 12 39 31 6 18 21 34 16 10 25 20 24 15 11 35 37 3 1 22 4 19 29 2 14 26 13 30 0 33 17 5 36 38 32
9 36 2 23 32 11 33 12 25 38 16 18 8 14 0 39 31 7 10 6 28 21 5 29 34 3 17 37 24 19 1 15 22 4 27 30 20 26 35 13
17 22 0 6 36 3 31 23 12 1 20 9 37 28 32 33 13 30 7 5 19 26 14 24 35 18 34 15 8 29 2 11 10 39 25 16 21 4 27 38
19 18 38 35 13 0 22 28 4 5 15 6 12 39 16 26 1 23 14 20 17 34 10 8 37 31 32 3 29 30 33 24 7 36 11 9 27 25 21 2
7 6 19 12 20 36 2 24 3 21 17 22 32 18 31 9 0 8 35 23 34 13 25 16 26 33 5 14 28 10 39 37 15 30 4 1 38 27 29 11
27 8 39 33 38 9 23 36 0 11 29 19 15 24 5 13 18 20 26 22 31 35 32 25 16 12 37 2 7 3 17 14 6 1 28 21 10 30 4 34
23 15 8 16 1 32 24 34 14 10 22 37 39 2 7 17 38 29 21 36 33 27 28 13 9 6 20 18 5 31 25 0 19 12 35 11 30 3 26 4
3 11 13 14 2 10 16 31 38 37 35 28 24 8 26 6 39 0 22 18 4 15 17 7 20 9 33 19 27 36 32 25 1 21 5 29 12 23 34 30
6 12 37 22 0 26 28 29 5 35 10 13 1 3 21 15 24 4 16 7 36 32 8 23 31 34 38 33 39 11 19 30 9 25 18 2 14 20 17 27
</pre>
=={{header|Julia}}==
Using the Python algorithm as described in the discussion section.
<
shufflerows(mat) = mat[shuffle(1:end), :]
Line 1,586 ⟶ 2,213:
printlatinsquare(5), println("\n"), printlatinsquare(5)
</
<pre>
1 3 0 4 2
Line 1,604 ⟶ 2,231:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun printSquare(latin: matrix) {
Line 1,661 ⟶ 2,288:
latinSquare(5)
latinSquare(10) // for good measure
}</
{{out}}
<pre>[4, 1, 2, 3, 0]
Line 1,694 ⟶ 2,321:
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.
<syntaxhighlight lang="m2000 interpreter">
Module FastLatinSquare {
n=5
Line 1,745 ⟶ 2,372:
End Sub
}
FastLatinSquare</
===Hard Way===
Line 1,754 ⟶ 2,381:
for 20X20 need 22 min (as for 9.8 version)
<syntaxhighlight lang="m2000 interpreter">
Module LatinSquare (n, z=1, f$="latin.dat", NewFile As Boolean=False) {
If Not Exist(f$) Or NewFile Then
Line 1,829 ⟶ 2,456:
LatinSquare 16
</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
Line 1,864 ⟶ 2,491:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
RandomLatinSquare[n_] := Module[{out, ord},
out = Table[RotateLeft[Range[n], i], {i, n}];
Line 1,872 ⟶ 2,499:
out
]
RandomLatinSquare[5] // Grid</
{{out}}
<pre>5 2 4 1 3
Line 1,886 ⟶ 2,513:
Starting at n = 11, the execution time will be very variable as the program proceeds by trial and error. At least, the algorithm will be able to produce all the possible Latin squares but not in a uniform way.
<
type LatinSquare = seq[seq[char]]
Line 1,929 ⟶ 2,556:
echo latinSquare(5)
echo latinSquare(5)
echo latinSquare(10)</
{{out}}
Line 1,954 ⟶ 2,581:
J A I C G B D H E F
E G F D C J B A H I</pre>
=={{header|Pascal}}==
Jacobson-Matthews algorithm. Generates uniformly distributed random Latin squares (if used PRNG is good - Delphi/Pascal built-in PRNG is '''not''').
Slightly modified translation of C code from https://brainwagon.org/2016/05/17/code-for-generating-a-random-latin-square/
Algorithm source:
Jacobson, M. T.; Matthews, P. (1996). "Generating uniformly distributed random latin squares". Journal of Combinatorial Designs. 4 (6): 405–437.
<syntaxhighlight lang="pascal">
{$APPTYPE CONSOLE}
const
Alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
Type
IncidenceCube = Array of Array Of Array of Integer;
Var
Cube : IncidenceCube;
DIM : Integer;
Procedure InitIncidenceCube(Var c:IncidenceCube; const Size:Integer);
var i, j, k : integer;
begin
DIM := Size;
SetLength(c,DIM,DIM,DIM);
for i := 0 to DIM-1 do
for j := 0 to DIM-1 do
for k := 0 to DIM-1 do c[i,j,k] := 0 ;
for i := 0 to DIM-1 do
for j := 0 to DIM-1 do c[i,j,(i+j) mod DIM] := 1;
end;
Procedure FreeIncidenceCube(Var c:IncidenceCube);
begin
Finalize(c);
end;
procedure PrintIncidenceCube(var c:IncidenceCube);
var i, j, k : integer;
begin
for i := 0 to DIM-1 do begin
for j := 0 to DIM-1 do begin
for k := 0 to DIM-1 do begin
if (c[i,j,k]=1) then begin
write(Alpha[k+1],' ');
break;
end;
end;
end;
Writeln;
end;
Writeln;
WriteLn;
end;
procedure ShuffleIncidenceCube(var c:IncidenceCube);
var i, j, rx, ry, rz, ox, oy, oz : integer;
begin
for i := 0 to (DIM*DIM*DIM)-1 do begin
repeat
rx := Random(DIM);
ry := Random(DIM);
rz := Random(DIM);
until (c[rx,ry,rz]=0);
for j := 0 to DIM-1 do begin
if (c[j,ry,rz]=1) then ox := j;
if (c[rx,j,rz]=1) then oy := j;
if (c[rx,ry,j]=1) then oz := j;
end;
Inc(c[rx,ry,rz]);
Inc(c[rx,oy,oz]);
Inc(c[ox,ry,oz]);
Inc(c[ox,oy,rz]);
Dec(c[rx,ry,oz]);
Dec(c[rx,oy,rz]);
Dec(c[ox,ry,rz]);
Dec(c[ox,oy,oz]);
while (c[ox,oy,oz] < 0) do begin
rx := ox ;
ry := oy ;
rz := oz ;
if (random(2)=0) then begin
for j := 0 to DIM-1 do begin
if (c[j,ry,rz]=1) then ox := j;
end;
end else begin
for j := DIM-1 downto 0 do begin
if (c[j,ry,rz]=1) then ox := j;
end;
end;
if (random(2)=0) then begin
for j := 0 to DIM-1 do begin
if (c[rx,j,rz]=1) then oy := j;
end;
end else begin
for j := DIM-1 downto 0 do begin
if (c[rx,j,rz]=1) then oy := j;
end;
end;
if (random(2)=0) then begin
for j := 0 to DIM-1 do begin
if (c[rx,ry,j]=1) then oz := j;
end;
end else begin
for j := DIM-1 downto 0 do begin
if (c[rx,ry,j]=1) then oz := j;
end;
end;
Inc(c[rx,ry,rz]);
Inc(c[rx,oy,oz]);
Inc(c[ox,ry,oz]);
Inc(c[ox,oy,rz]);
Dec(c[rx,ry,oz]);
Dec(c[rx,oy,rz]);
Dec(c[ox,ry,rz]);
Dec(c[ox,oy,oz]);
end;
end;
end;
begin
Randomize;
InitIncidenceCube(cube, 5); ShuffleIncidenceCube(cube); PrintIncidenceCube(cube); FreeIncidenceCube(Cube);
InitIncidenceCube(cube, 5); ShuffleIncidenceCube(cube); PrintIncidenceCube(cube); FreeIncidenceCube(Cube);
InitIncidenceCube(cube,10); ShuffleIncidenceCube(cube); PrintIncidenceCube(cube); FreeIncidenceCube(Cube);
InitIncidenceCube(cube,26); ShuffleIncidenceCube(cube); PrintIncidenceCube(cube); FreeIncidenceCube(Cube);
end.
</syntaxhighlight>
{{out}}
<pre>
B A E D C
D B C A E
C D A E B
A E B C D
E C D B A
A C D B E
B E C D A
D A B E C
E D A C B
C B E A D
E F G C D A H B I J
B J A H F D C E G I
F I J A C E G H D B
J A E D G F B I C H
C E D I H G A J B F
I D H E A B F C J G
H G B J E C I D F A
G C F B J I D A H E
D H I F B J E G A C
A B C G I H J F E D
W D X Q V Z S A O T P K C Y M H J L F R U B I E N G
E J R T D G P U C H F Y B Q W V I Z K L S X O N M A
Y E B A W I T J U Z H F N G P L X M R K D Q C V S O
H V F W Y S E P A N X M R O Q K B C L G J U T Z I D
C Y E I G Q D X T S J L U M K B V P Z H N A F O R W
L G J R O X F Q Y K C E W U V S A B D P H N Z I T M
B M G D N F I R Z E L H Q K J U O T V C X Y A P W S
G Z H S U L Q C K X Y V F I A O W J B M P R N T D E
K O W L C T U I P V R A J N S E Z H X D M F G B Q Y
D R A H X C K E W L S N V Z O P F Q Y T G M B J U I
V Q Y O R D G B X U Z T H J E F K S C N I W M A P L
U C M B A R Z F J O T G K X D N P I Q W L S V Y E H
Z F N U T V M H R Q I B S P X D C A W E O L Y G K J
J N D V M B X Z F C G O I S Y R L E P A W T K U H Q
N T L Y S P J O B G D W E C Z I R F U X V H Q M A K
A I C P J H B W Q D E S M R L Z G N T V Y K U F O X
R K S N E W A V L M Q D G H T C Y U I F B O P X J Z
O W I M F K R Y H B A Q X D U T N V G J Z P E S L C
P B T X Q U N L S Y M I O W F J H K E Z A G D C V R
X L U K I E H M N A B Z P V G W D Y S O R C J Q F T
M H Z C K J Y T I F O P D A B X U W N S Q E R L G V
Q S P G H Y O N V W U R A L C M T D J I E Z X K B F
I A O F P M L K D J W U Z E N G Q X H Y T V S R C B
T P K E B A V D G I N X L F R Y S O M Q C J H W Z U
S U V Z L O C G M P K J Y T I Q E R A B F D W H X N
F X Q J Z N W S E R V C T B H A M G O U K I L D Y P
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 1,989 ⟶ 2,827:
}
say display random_ls($_) for 2..5, 5;</
{{out}}
<pre>B A
Line 2,017 ⟶ 2,855:
=={{header|Phix}}==
Brute force, begins to struggle above 42.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">aleph</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"</span>
Line 2,083 ⟶ 2,921:
<span style="color: #000000;">latin_square</span><span style="color: #0000FF;">(</span><span style="color: #000000;">42</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
{{out}}
<pre>
Line 2,170 ⟶ 3,008:
Normally a non-random value strategy is preferred such as <code>up</code>, <code>split</code>, or <code>updown</code>, but the task requires random solutions.
<
_ = random2(), % random seed
N = 5,
Line 2,205 ⟶ 3,043:
nl
end,
nl.</
{{out}}
Line 2,287 ⟶ 3,125:
===Number of solutions===
The number of solutions for a Latin square of size N is the OEIS sequence [https://oeis.org/A002860 A002860: Number of Latin squares of order n; or labeled quasigroups]. Here we check N = 1..6 which took 18min54s.
<
foreach(N in 1..6)
Count = count_all(latin_square(N,_)),
println(N=Count)
end.</
{{out}}
Line 2,306 ⟶ 3,144:
=={{header|Python}}==
<
from copy import deepcopy
Line 2,366 ⟶ 3,204:
print(_to_text(square))
_check(square)
print()</
{{out}}
Line 2,401 ⟶ 3,239:
4 10 9 0 3 7 2 5 1 11 6 8
0 6 11 9 1 3 5 10 2 7 8 4</pre>
=={{header|Quackery}}==
<code>transpose</code> is defined at [[Matrix transposition#Quackery]].
<syntaxhighlight lang="Quackery"> [ [] []
rot times
[ i join ]
dup size times
[ tuck
nested join
swap
behead join ]
drop
shuffle
transpose
shuffle ] is rls ( n --> [ )
2 times
[ 5 rls
witheach
[ witheach
[ echo sp ]
cr ]
cr ]</syntaxhighlight>
{{out}}
<pre>2 4 0 1 3
0 2 3 4 1
1 3 4 0 2
4 1 2 3 0
3 0 1 2 4
1 2 3 0 4
3 4 0 2 1
2 3 4 1 0
0 1 2 4 3
4 0 1 3 2
</pre>
=={{header|Raku}}==
Line 2,407 ⟶ 3,285:
{{trans|Python}}
<syntaxhighlight lang="raku"
sub random ( @ls, :$size = 5 ) {
Line 2,441 ⟶ 3,319:
# Or, if you'd prefer:
display random latin-square, :size($_) for 12, 2, 1;</
{{out|Sample output}}
<pre> V Z M J U
Line 2,491 ⟶ 3,369:
The symbols could be any characters (except those that contain a blank), but the numbers from '''0''' ──► '''N-1''' are used.
<
parse arg N seed . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 5 /*Not specified? Then use the default.*/
Line 2,506 ⟶ 3,384:
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. */</
{{out|output|text= for 1<sup>st</sup> run when using the default inputs:}}
<pre>
Line 2,525 ⟶ 3,403:
=={{header|Ring}}==
<
load "stdlib.ring"
load "guilib.ring"
Line 2,871 ⟶ 3,749:
###====================================================================================
</syntaxhighlight>
[https://www.mediafire.com/file/6fruvfgydnbmtyj/RandomLatinSquares.jpg/file Random Latin Squares - image]
=={{header|RPL}}==
{{trans|Quackery}}
{{works with|RPL|HP49-C}}
<code>SHUFL</code> is defined at [[Knuth shuffle#RPL|Knuth shuffle]]
« → n
« « k » 'k' 0 n 1 - 1 SEQ
2 n '''START'''
DUP TAIL LASTARG HEAD +
'''NEXT'''
n →LIST
<span style="color:blue">SHUFL</span> AXL
TRAN AXL
<span style="color:blue">SHUFL</span> AXL
» '<span style="color:blue">RLS</span>' STO
5 <span style="color:blue">RLS</span>
{{out}}
<pre>
1: [[ 3 1 4 2 0 ]
[ 4 2 0 3 1 ]
[ 2 0 3 1 4 ]
[ 0 3 1 4 2 ]
[ 1 4 2 0 3 ]]
</pre>
=={{header|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.
<
def generate_square
Line 2,896 ⟶ 3,799:
2.times{print_square( generate_square)}
</syntaxhighlight>
{{out}}<pre>
3 4 2 1 5
Line 2,915 ⟶ 3,818:
{{trans|Go}}
===Restarting Row method===
<
var rand = Random.new()
Line 2,974 ⟶ 3,877:
latinSquare.call(5)
latinSquare.call(5)
latinSquare.call(10) // for good measure</
{{out}}
Line 3,007 ⟶ 3,910:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<
import "./sort" for Sort
import "./fmt" for Fmt
import "./math" for Int
var rand = Random.new()
Line 3,222 ⟶ 4,125:
for (i in 0..3) System.print("%(testSquares[i]) : %(counts[i])")
System.print("\nA randomly generated latin square of order 6 is:\n")
generateLatinSquares.call(6, 1, 1)</
{{out}}
Line 3,261 ⟶ 4,164:
=={{header|zkl}}==
<
if(n<=0) return(T);
square,syms := List(), symbols.walker().walk(n);
Line 3,268 ⟶ 4,171:
T.zip(square.shuffle().xplode()).shuffle();
}
fcn rls2String(square){ square.apply("concat"," ").concat("\n") }</
<
randomLatinSquare(5, ["A".."Z"]) : rls2String(_).println("\n");
randomLatinSquare(10,"!@#$%^&*()") : rls2String(_).println("\n");</
{{out}}
<pre>
| |||