Random Latin squares: Difference between revisions
Added Algol 68
(Latin Squares selected at random uniformly) |
(Added Algol 68) |
||
Line 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 ios 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>
| |||