Random Latin squares: Difference between revisions

{{trans|Python}}

 

assert(matrix.len == matrix[0].len)

V r = [[0] * matrix.len] * matrix.len

print(square.map(row -> row.join(‘ ’)).join("\n"))

_check(square)

 

{{out}}

 

=={{header|Action!}}==

DEFINE DIMENSION="5"

 

PutE()

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Random_Latin_squares.png Screenshot from Atari 8-bit computer]

=={{header|Arturo}}==

 

square: new []

variants: shuffle permutate 0..n-1

print row

print "---------"

 

{{out}}

=={{header|C}}==

{{trans|C++}}

#include <stdio.h>

#include <stdlib.h>

 

return 0;

{{out}}

<pre>[1, 4, 3, 0, 2]

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

{{trans|Java}}

#include <chrono>

#include <iostream>

latinSquare(10);

return 0;

{{out}}

<pre>[4, 3, 1, 2, 0]

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

{{trans|Kotlin}}

using System.Collections.Generic;

 

}

}

{{out}}

<pre>[3, 0, 1, 4, 2]

=={{header|D}}==

{{trans|C#}}

import std.random;

import std.stdio;

 

latinSquare(10);

{{out}}

<pre>[2, 4, 3, 1, 0]

=={{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]]. This solution generates completely random uniformly distributed Latin Squares from all possible Latin Squares of order 5. It takes 5 thousandths of a second can that really be called hard?

// 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()

{{out}}

<pre>

=={{header|Factor}}==

A brute force method for generating uniformly random Latin squares. Repeatedly select a random permutation of (0, 1,...n-1) and add it as the next row of the square. If at any point the rules for being a Latin square are violated, start the entire process over again from the beginning.

prettyprint random sequences sets ;

IN: rosetta-code.random-latin-squares

: random-latin-squares ( -- ) [ 5 ls simple-table. nl ] twice ;

 

{{out}}

<pre>

===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 (

latinSquare(5)

latinSquare(10) // for good measure

 

{{out}}

===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 (

fmt.Println("\nA randomly generated latin square of order 6 is:\n")

generateLatinSquares(6, 1, 1)

 

{{out}}

given first row and first column.

 

 

latinSquare :: Eq a => [a] -> [a] -> [[a]]

putStrLn $

unlines $

 

<pre>λ> printTable $ latinSquare [1,2,3,4,5] [1,3,2,5,4]

the deterministic algorithm.

 

randomLatinSquare set = do

r <- randomPermutation set

c <- randomPermutation (tail r)

 

For examples a naive linear congruent method in a State monad is used.

 

 

type Random a = State Int a

 

randomSample :: [a] -> Random a

 

<pre>λ> printTable $ randomLatinSquare [0..4] `evalState` 42

 

=={{header|J}}==

s=. ?~ y NB. "deal" y unique integers from 0 to y

for_ijk. i.<:y do.

end.

)

{{out}}

<pre> rls 5

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.Collections;

import java.util.Iterator;

latinSquare(10);

}

{{out}}

<pre>[1, 3, 4, 0, 2]

 

=={{header|Javascript}}==

class Latin {

constructor(size = 3) {

}

new Latin(5);

{{out}}

<pre>

=={{header|Julia}}==

Using the Python algorithm as described in the discussion section.

 

shufflerows(mat) = mat[shuffle(1:end), :]

 

printlatinsquare(5), println("\n"), printlatinsquare(5)

<pre>

1 3 0 4 2

=={{header|Kotlin}}==

{{trans|Go}}

 

fun printSquare(latin: matrix) {

latinSquare(5)

latinSquare(10) // for good measure

{{out}}

<pre>[4, 1, 2, 3, 0]

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.

 

Module FastLatinSquare {

n=5

End Sub

}

 

===Hard Way===

for 20X20 need 22 min (as for 9.8 version)

 

Module LatinSquare (n, z=1, f$="latin.dat", NewFile As Boolean=False) {

If Not Exist(f$) Or NewFile Then

LatinSquare 16

 

{{out}}

<pre style="height:30ex;overflow:scroll">

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

RandomLatinSquare[n_] := Module[{out, ord},

out = Table[RotateLeft[Range[n], i], {i, n}];

out

]

{{out}}

<pre>5 2 4 1 3

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]]

echo latinSquare(5)

echo latinSquare(5)

 

{{out}}

Jacobson, M. T.; Matthews, P. (1996). "Generating uniformly distributed random latin squares". Journal of Combinatorial Designs. 4 (6): 405–437.

 

 

{$APPTYPE CONSOLE}

end.

 

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

}

 

{{out}}

<pre>B A

=={{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>

<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>

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,

nl

end,

 

{{out}}

===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)

 

{{out}}

 

=={{header|Python}}==

from copy import deepcopy

 

print(_to_text(square))

_check(square)

 

{{out}}

{{trans|Python}}

 

 

sub random ( @ls, :$size = 5 ) {

 

# Or, if you'd prefer:

{{out|Sample output}}

<pre> V Z M J U

 

The symbols could be any characters (except those that contain a blank), &nbsp; but the numbers from &nbsp; '''0''' ──► '''N-1''' &nbsp; are used.

parse arg N seed . /*obtain the optional argument from CL.*/

if N=='' | N=="," then N= 5 /*Not specified? Then use the default.*/

do j=1 for N /* [↓] display rows of random Latin sq*/

say translate(subword(zz, j, N), , '_') /*translate leading underbar to blank. */

{{out|output|text=&nbsp; for 1^st run when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

load "stdlib.ring"

load "guilib.ring"

###====================================================================================

 

 

[https://www.mediafire.com/file/6fruvfgydnbmtyj/RandomLatinSquares.jpg/file Random Latin Squares - image]

=={{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

 

2.times{print_square( generate_square)}

{{out}}<pre>

3 4 2 1 5

{{trans|Go}}

===Restarting Row method===

 

var rand = Random.new()

latinSquare.call(5)

latinSquare.call(5)

 

{{out}}

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

import "/sort" for Sort

import "/fmt" for Fmt

for (i in 0..3) System.print("%(testSquares[i]) : %(counts[i])")

System.print("\nA randomly generated latin square of order 6 is:\n")

 

{{out}}

 

=={{header|zkl}}==

if(n<=0) return(T);

square,syms := List(), symbols.walker().walk(n);

T.zip(square.shuffle().xplode()).shuffle();

}

randomLatinSquare(5, ["A".."Z"]) : rls2String(_).println("\n");

{{out}}

<pre>