Latin Squares in reduced form: Difference between revisions
added solution for d
(added solution for d) |
|||
Line 7:
* displaying the four reduced Latin Squares of order 4.
* for n = 1 to 6 (or more) produce the set of reduced Latin Squares; produce a table which shows the size of the set of reduced Latin Squares and compares this value times n! times (n-1)! with the values in [http://oeis.org/A002860 OEIS A002860].
=={{header|D}}==
{{trans|Go}}
<lang d>import std.algorithm;
import std.array;
import std.range;
import std.stdio;
alias matrix = int[][];
auto dList(int n, int start) {
start--; // use 0 basing
auto a = iota(0, n).array;
a[start] = a[0];
a[0] = start;
sort(a[1..$]);
auto first = a[1];
// recursive closure permutes a[1:]
matrix r;
void recurse(int last) {
if (last == first) {
// bottom of recursion. you get here once for each permutation.
// test if permutation is deranged.
foreach (j,v; a[1..$]) {
if (j + 1 == v) {
return; //no, ignore it
}
}
// yes, save a copy with 1 based indexing
auto b = a.map!"a+1".array;
r ~= b;
return;
}
for (int i = last; i >= 1; i--) {
swap(a[i], a[last]);
recurse(last -1);
swap(a[i], a[last]);
}
}
recurse(n - 1);
return r;
}
ulong reducedLatinSquares(int n, bool echo) {
if (n <= 0) {
if (echo) {
writeln("[]\n");
}
return 0;
} else if (n == 1) {
if (echo) {
writeln("[1]\n");
}
return 1;
}
matrix rlatin = uninitializedArray!matrix(n);
foreach (i; 0..n) {
rlatin[i] = uninitializedArray!(int[])(n);
}
// first row
foreach (j; 0..n) {
rlatin[0][j] = j + 1;
}
ulong count;
void recurse(int i) {
auto rows = dList(n, i);
outer:
foreach (r; 0..rows.length) {
rlatin[i-1] = rows[r].dup;
foreach (k; 0..i-1) {
foreach (j; 1..n) {
if (rlatin[k][j] == rlatin[i - 1][j]) {
if (r < rows.length - 1) {
continue outer;
}
if (i > 2) {
return;
}
}
}
}
if (i < n) {
recurse(i + 1);
} else {
count++;
if (echo) {
printSquare(rlatin, n);
}
}
}
}
// remaining rows
recurse(2);
return count;
}
void printSquare(matrix latin, int n) {
foreach (row; latin) {
writeln(row);
}
writeln;
}
ulong factorial(ulong n) {
if (n == 0) {
return 1;
}
ulong prod = 1;
foreach (i; 2..n+1) {
prod *= i;
}
return prod;
}
void main() {
writeln("The four reduced latin squares of order 4 are:\n");
reducedLatinSquares(4, true);
writeln("The size of the set of reduced latin squares for the following orders");
writeln("and hence the total number of latin squares of these orders are:\n");
foreach (n; 1..7) {
auto size = reducedLatinSquares(n, false);
auto f = factorial(n - 1);
f *= f * n * size;
writefln("Order %d: Size %-4d x %d! x %d! => Total %d", n, size, n, n - 1, f);
}
}</lang>
{{out}}
<pre>The four 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, 4, 1, 3]
[3, 1, 4, 2]
[4, 3, 2, 1]
[1, 2, 3, 4]
[2, 3, 4, 1]
[3, 4, 1, 2]
[4, 1, 2, 3]
The size of the set of reduced latin squares for the following orders
and hence the total number of latin squares of these orders are:
Order 1: Size 1 x 1! x 0! => Total 1
Order 2: Size 1 x 2! x 1! => Total 2
Order 3: Size 1 x 3! x 2! => Total 12
Order 4: Size 4 x 4! x 3! => Total 576
Order 5: Size 56 x 5! x 4! => Total 161280
Order 6: Size 9408 x 6! x 5! => Total 812851200</pre>
=={{header|F_Sharp|F#}}==
| |||