Random Latin squares: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 1,555:
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.'''
The jq program presented in this section uses the Knuth shuttle for
the first row, and then adds cells one-by-one by making a calculated
but fallible selection based on the values in its row and column,
backtracking on failure. The method ensures uniform randomness and
scales quite well, though the running time is quite variable.
For example, to generate a Latin Square of order 10 (LS(10)) typically
takes from 0.11 to 0.14 seconds (u+s) on my 3GHz machine. By comparison,
the Go program on this page using the "Reduced Form" method for
achieving uniform randomness is far more complicated and takes much
longer - execution was terminated after 50 minutes.
To generate LS(15), the jq program typically takes 0.15 to 0.21s; to
generate LS(20) takes from about 0.36 to 0.94 seconds; and LS(30)
about 0.5 to 29 seconds.
The program presented here used /dev/random as its source of entropy.
<syntaxhighlight lang=sh>
#!/bin/bash
< /dev/random tr -cd '0-9' | fold -w 1 | $jq -Mcnr -f random-latin-squares.jq
</syntaxhighlight>
'''random-latin-squares.jq'''
<syntaxhighlight lang=sh>
### Generic Utility Functions
# 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]];
# 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]) | extend # n.b.
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, "\nTwelve", 12
| printLatinSquare
'
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
| |||