Latin Squares in reduced form: Difference between revisions

=={{header|jq}}==

{{works with|jq}}

'''Works with recent versions of gojq''' (e.g. f0faa22 (August 22, 2021))

''' Preliminaries'''

<lang jq>def count(s): reduce s as $x (0; .+1);

def factorial: reduce range(2;.+1) as $i (1; . * $i);

def permutations:

if length == 0 then []

else

range(0;length) as $i

| [.[$i]] + (del(.[$i])|permutations)

end ;

</lang>

'''Latin Squares'''

<lang jq>def clash($row2; $row1):

any(range(0;$row2|length); $row1[.] == $row2[.]);

# Input is a row; stream is a stream of rows

def clash(stream):

. as $row | any(stream; clash($row; .)) ;

# Emit a stream of latin squares of size .

def latin_squares:

. as $n

# Emit a stream of arrays of permutation of 1 .. $n inclusive, and beginning with $i

| def permutations_beginning_with($i):

[$i] + ([range(1; $i), range($i+1; $n + 1)] | permutations);

# input: an array of rows, $rows

# output: a stream of all the permutations starting with $i

# that are permissible relative to $rows

def filter_permuted($i):

. as $rows

| permutations_beginning_with($i)

| select( clash($rows[]) | not ) ;

# input: an array of the first few rows (at least one) of a latin square

# output: a stream of possible immediate-successor rows

def next_latin_square_row:

filter_permuted(1 + .[-1][0]);

# recursion makes completing a latin square a snap

def complete_latin_square:

if length == $n then .

else next_latin_square_row as $next

| . + [$next] | complete_latin_square

end;

[[range(1;$n+1)]]

| complete_latin_square ;

</lang>

'''The Task'''

<lang jq>def task:

"The reduced latin squares of order 4 are:",

(4 | latin_squares),

"",

(range(1; 7)

| . as $i

| count(latin_squares) as $c

| ($c * factorial * ((.-1)|factorial)) as $total

| "There are \($c) reduced latin squares of order \(.); \($c) * \(.)! * \(.-1)! is \($total)"

) ;

task</lang>

{{out}}

Invocation: jq -nrc -f latin-squares.jq

<pre>

The reduced latin squares of order 4 are:

[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]]

[[1,2,3,4],[2,1,4,3],[3,4,2,1],[4,3,1,2]]

[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

[[1,2,3,4],[2,4,1,3],[3,1,4,2],[4,3,2,1]]

There are 1 reduced latin squares of order 1; 1 * 1! * 0! is 1

There are 1 reduced latin squares of order 2; 1 * 2! * 1! is 2

There are 1 reduced latin squares of order 3; 1 * 3! * 2! is 12

There are 4 reduced latin squares of order 4; 4 * 4! * 3! is 576

There are 56 reduced latin squares of order 5; 56 * 5! * 4! is 161280

There are 9408 reduced latin squares of order 6; 9408 * 6! * 5! is 812851200

</pre>