Latin Squares in reduced form: Difference between revisions

{{trans|Python}}

 

start--

V a = Array(0 .< n)

V first = a[1]

[[Int]] r

I (last == @first)

L(v) @a[1..]

 

V count = 0

V rows = dList(@n, i)

 

V f = factorial(n - 1)

f *= f * n * size

 

{{out}}

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>The four reduced latin squares of order 4 are:

=={{header|C++}}==

{{trans|C#}}

#include <functional>

#include <iostream>

 

return 0;

{{out}}

<pre>The four reduced lating squares of order 4 are:

=={{header|D}}==

{{trans|Go}}

import std.array;

import std.range;

writefln("Order %d: Size %-4d x %d! x %d! => Total %d", n, size, n, n - 1, f);

}

{{out}}

<pre>The four reduced latin squares of order 4 are:

===The Function===

This task uses [[Permutations/Derangements#F.23]]

// Generate Latin Squares in reduced form. Nigel Galloway: July 10th., 2019

let normLS α=

let rec normLS n g=seq{for i in fG n N.[g] do if g=α-2 then yield [|1..α|]::(List.rev (i::n)) else yield! normLS (i::n) (g+1)}

match α with 1->seq[[[|1|]]] |2-> seq[[[|1;2|];[|2;1|]]] |_->Seq.collect(fun n->normLS [n] 1) N.[0]

===The Task===

normLS 4 |> Seq.iter(fun n->List.iter(printfn "%A") n;printfn "");;

{{out}}

<pre>

[|4; 3; 2; 1|]

</pre>

let rec fact n g=if n<2 then g else fact (n-1) n*g

[1..6] |> List.iter(fun n->let nLS=normLS n|>Seq.length in printfn "order=%d number of Reduced Latin Squares nLS=%d nLS*n!*(n-1)!=%d" n nLS (nLS*(fact n 1)*(fact (n-1) 1)))

{{out}}

<pre>

=={{header|Go}}==

This reuses the dList function from the [[Permutations/Derangements#Go]] task, suitably adjusted for the present one.

 

import (

fmt.Printf("Order %d: Size %-4d x %d! x %d! => Total %d\n", n, size, n, n-1, f)

}

 

{{out}}

The solution uses permutation generator given by '''Data.List''' package and List monad for generating all possible latin squares as a fold of permutation list.

 

import Control.Monad (foldM, forM_)

 

printTable :: Show a => [[a]] -> IO ()

printTable tbl = putStrLn $ unlines $ unwords . map show <$> tbl

 

It is slightly optimized by grouping permutations by the first element according to a set order. Partitioning reduces the filtering procedure by factor of an initial set size.

 

'''Tasks'''

putStrLn "Latin squares of order 4:"

mapM_ printTable $ latinSquares [1..4]

total = fact n * fact (n-1) * size

fact i = product [1..i]

 

<pre>λ> task1 >> task2

Order 5: 56*5!*4!=161280

Order 6: 9408*6!*5!=812851200</pre>

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

 

}

 

{{out}}

 

''' Preliminaries'''

 

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

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

end ;

'''Latin Squares'''

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

 

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

| complete_latin_square ;

'''The Task'''

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

(4 | latin_squares),

) ;

 

{{out}}

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

 

=={{header|Julia}}==

 

clash(row2, row1::Vector{Int}) = any(i -> row1[i] == row2[i], 1:length(row2))

testlatinsquares()

<pre>

The four reduced latin squares of order 4 are:

=={{header|Kotlin}}==

{{trans|D}}

 

fun dList(n: Int, sp: Int): Matrix {

println("Order $n: Size %-4d x $n! x ${n - 1}! => Total $f".format(size))

}

{{out}}

<pre>The four reduced latin squares of order 4 are:

=={{header|MiniZinc}}==

===The Model (lsRF.mnz)===

%Latin Squares in Reduced Form. Nigel Galloway, September 5th., 2019

include "alldifferent.mzn";

array[1..N,1..N] of var 1..N: p; constraint forall(n in 1..N)(p[1,n]=n /\ p[n,1]=n);

constraint forall(n in 1..N)(alldifferent([p[n,g]|g in 1..N])/\alldifferent([p[g,n]|g in 1..N]));

===The Tasks===

;displaying the four reduced Latin Squares of order 4

include "lsRF.mzn";

output [show_int(1,p[i,j])++

else "" endif

| i,j in 1..4 ] ++ ["\n"];

When the above is run using minizinc --all-solutions -DN=4 the following is produced:

{{out}}

We use the Go algorithm but have chosen to create two types, Row and Matrix, to simulate sequences starting at index 1. So, the indexes and tests are somewhat different.

 

 

type

let size = reducedLatinSquares(n, false)

let f = fac(n - 1)^2 * n * size

 

{{out}}

=={{header|Perl}}==

It takes a little under 2 minutes to find order 7.

 

use strict; # https://rosettacode.org/wiki/Latin_Squares_in_reduced_form

length $s <= 1 ? $s :

map { my $f = $_; map "$f$_", perm( $s =~ s/$_//r ) } split //, $s;

{{out}}

<pre>

A Simple backtracking search.<br>

aside: in phix here is no difference between res[r][c] and res[r,c]. I mixed them here, using whichever felt the more natural to me.

<span style="color: #004080;">string</span> <span style="color: #000000;">aleph</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Order %d: Size %-4d x %d! x %d! =&gt; Total %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">size</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

"2 minutes and 23s"

</pre>

 

=={{header|Python}}==

{{trans|D}}

start -= 1 # use 0 basing

a = range(n)

f = factorial(n - 1)

f *= f * n * size

{{out}}

<pre>The four reduced latin squares of order 4 are:

=={{header|Raku}}==

(formerly Perl 6)

sub postfix:<!>($n) { (constant f = 1, |[\×] 1..*)[$n] }

sub prefix:<!>($n) { (1, 0, 1, -> $a, $b { ($++ + 2) × ($b + $a) } ... *)[$n] }

for 1..6 -> $n {

printf "Order $n: Size %-4d x $n! x {$n-1}! => Total %d\n", $_, $_ * $n! * ($n-1)! given LS-reduced($n).elems

{{out}}

<pre>1 2 3 4

=={{header|Ruby}}==

{{trans|D}}

for row in a

print row, "\n"

f = f * f * n * size

print "Order %d Size %-4d x %d! x %d! => Total %d\n" % [n, size, n, n - 1, f]

{{out}}

<pre>The four reduced latin squares of order 4 are:

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Imports Matrix = System.Collections.Generic.List(Of System.Collections.Generic.List(Of Integer))

End Sub

 

{{out}}

<pre>The four reduced latin squares of order 4 are:

{{libheader|Wren-math}}

{{libheader|Wren-fmt}}

 

// generate derangements of first n numbers, with 'start' in first place.

f = f * f * n * size

Fmt.print("Order $d: Size $-4d x $d! x $d! => Total $d", n, size, n, n-1, f)

 

{{out}}

{{trans|Go}}

This reuses the dList function from the [[Permutations/Derangements#zkl]] task, suitably adjusted for the present one.

if(n<=1) return(n);

rlatin:=n.pump(List(), List.createLong(n,0).copy); // matrix of zeros

println();

}

reducedLatinSquare(4,True);

 

size,f,f := reducedLatinSquare(n), fact(n - 1), f*f*n*size;;

println("Order %d: Size %-4d x %d! x %d! -> Total %,d".fmt(n,size,n,n-1,f));

{{out}}

<pre>