Latin Squares in reduced form: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 9:
<br><br>
=={{header|C
{{trans|D}}
<lang csharp>using System;
Line 348 ⟶ 165:
<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|C++}}==
{{trans|C#}}
<lang cpp>#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
typedef std::vector<std::vector<int>> matrix;
matrix dList(int n, int start) {
start--; // use 0 basing
std::vector<int> a(n);
std::iota(a.begin(), a.end(), 0);
a[start] = a[0];
a[0] = start;
std::sort(a.begin() + 1, a.end());
auto first = a[1];
// recursive closure permutes a[1:]
matrix r;
std::function<void(int)> recurse;
recurse = [&](int last) {
if (last == first) {
// bottom of recursion you get here once for each permutation.
// test if permutation is deranged.
for (size_t j = 1; j < a.size(); j++) {
auto v = a[j];
if (j == v) {
return; //no, ignore it
}
}
// yes, save a copy with 1 based indexing
std::vector<int> b;
std::transform(a.cbegin(), a.cend(), std::back_inserter(b), [](int v) { return v + 1; });
r.push_back(b);
return;
}
for (int i = last; i >= 1; i--) {
std::swap(a[i], a[last]);
recurse(last - 1);
std::swap(a[i], a[last]);
}
};
recurse(n - 1);
return r;
}
void printSquare(const matrix &latin, int n) {
for (auto &row : latin) {
auto it = row.cbegin();
auto end = row.cend();
std::cout << '[';
if (it != end) {
std::cout << *it;
it = std::next(it);
}
while (it != end) {
std::cout << ", " << *it;
it = std::next(it);
}
std::cout << "]\n";
}
std::cout << '\n';
}
unsigned long reducedLatinSquares(int n, bool echo) {
if (n <= 0) {
if (echo) {
std::cout << "[]\n";
}
return 0;
} else if (n == 1) {
if (echo) {
std::cout << "[1]\n";
}
return 1;
}
matrix rlatin;
for (int i = 0; i < n; i++) {
rlatin.push_back({});
for (int j = 0; j < n; j++) {
rlatin[i].push_back(j);
}
}
// first row
for (int j = 0; j < n; j++) {
rlatin[0][j] = j + 1;
}
unsigned long count = 0;
std::function<void(int)> recurse;
recurse = [&](int i) {
auto rows = dList(n, i);
for (size_t r = 0; r < rows.size(); r++) {
rlatin[i - 1] = rows[r];
for (int k = 0; k < i - 1; k++) {
for (int j = 1; j < n; j++) {
if (rlatin[k][j] == rlatin[i - 1][j]) {
if (r < rows.size() - 1) {
goto outer;
}
if (i > 2) {
return;
}
}
}
}
if (i < n) {
recurse(i + 1);
} else {
count++;
if (echo) {
printSquare(rlatin, n);
}
}
outer: {}
}
};
//remaining rows
recurse(2);
return count;
}
unsigned long factorial(unsigned long n) {
if (n <= 0) return 1;
unsigned long prod = 1;
for (unsigned long i = 2; i <= n; i++) {
prod *= i;
}
return prod;
}
int main() {
std::cout << "The four reduced lating squares of order 4 are:\n";
reducedLatinSquares(4, true);
std::cout << "The size of the set of reduced latin squares for the following orders\n";
std::cout << "and hence the total number of latin squares of these orders are:\n\n";
for (int n = 1; n < 7; n++) {
auto size = reducedLatinSquares(n, false);
auto f = factorial(n - 1);
f *= f * n * size;
std::cout << "Order " << n << ": Size " << size << " x " << n << "! x " << (n - 1) << "! => Total " << f << '\n';
}
return 0;
}</lang>
{{out}}
<pre>The four reduced lating squares of order 4 are:
[1, 2, 3, 4]
[2, 1, 4, 3]
Line 1,333:
%%%mzn-stat: nSolutions=9408
</pre>
The only way to complete the tasks requirement to produce a table is with another language. Ruby has the ability to run an external program, capture the output, and text handling ability to format it to this tasks requirements. Othe scripting languages are available.
=={{header|Phix}}==
A Simple backtracking search.<br>
Line 1,457 ⟶ 1,458:
Order 6: Size 9408 x 6! x 5! => Total 812851200
</pre>
=={{header|Python}}==
Line 1,642 ⟶ 1,583:
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|Raku}}==
(formerly Perl 6)
<lang perl6># utilities: factorial, sub-factorial, derangements
sub postfix:<!>($n) { (constant f = 1, |[\×] 1..*)[$n] }
sub prefix:<!>($n) { (1, 0, 1, -> $a, $b { ($++ + 2) × ($b + $a) } ... *)[$n] }
sub derangements(@l) { @l.permutations.grep(-> @p { none(@p Zeqv @l) }) }
sub LS-reduced (Int $n) {
return [1] if $n == 1;
my @LS;
my @l = 1 X+ ^$n;
my %D = derangements(@l).classify(*.[0]);
for [X] (^(!$n/($n-1))) xx $n-1 -> $tuple {
my @d.push: @l;
@d.push: %D{2}[$tuple[0]];
LOOP:
for 3 .. $n -> $x {
my @try = |%D{$x}[$tuple[$x-2]];
last LOOP if any @try »==« @d[$_] for 1..@d-1;
@d.push: @try;
}
next unless @d == $n and [==] [Z+] @d;
@LS.push: @d;
}
@LS
}
say .join("\n") ~ "\n" for LS-reduced(4);
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
}</lang>
{{out}}
<pre>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
Order 1: Size 1 x 1! x 0! => Total 1
| |||